티스토리

rudgh99

검색하기

블로그 홈

rudgh99

algorithmjjangdol.tistory.com/m

컴퓨터와 친해지고 싶은 사람의 잡다한 기록

구독자: 1

방명록 방문하기

주요 글 목록

[BOJ] 10816번 : 숫자 카드 2 1. problem : https://www.acmicpc.net/problem/10816 2. solution 1 : #include using namespace std;int n, m; vector v1; vector v2; vector ans; int lower_search_func(int& a) { int left = 0, right = n; while (left = a) right = mid; else left = mid + 1; } return left; }int upper_search_func(int& a) { int left = 0, right = n; while (left > n; for (int i = 0; i > x; v1.push_back(x); } cin >> m; f.. 공감수 1 댓글수 1 2024. 11. 13.
[BOJ] 1920번 : 수 찾기 1. problem : https://www.acmicpc.net/problem/1920 2. solution 1 :#include using namespace std;int N, M; vector v1; vector v2; bool find_num(int& a) { int left = 0; int right = N-1; while (left > N; for (int i = 0; i > x; v1.push_back(x); } sort(v1.begin(), v1.end()); cin >> M; for (int i = 0; i > x; v2.push_back(x); } for (int i = 0; i binary search를 이용해 답을 도출했다. binary search를 하기 위해서는 .. 공감수 0 댓글수 1 2024. 10. 31.
[BOJ] 1038번 : 감소하는 수 1. problem : https://www.acmicpc.net/problem/1038 2. solution 1 :#include using namespace std;vector v(10, 0);int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int cnt = 0; for (int i = 1; i source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/1038.cpp basic-algo-lecture/0x12/solutions/1038.cpp at master · encrypted-def/basic-algo.. 공감수 1 댓글수 2 2024. 10. 11.
[BOJ] 1011번 : Fly me to the Alpha Centauri 1. problem : https://www.acmicpc.net/problem/1011 2. solution 1 :#include using namespace std;long long func(long long a) { return (2 * sqrt(a) - 1e-9);}int main(void) { ios::sync_with_stdio(0); cin.tie(0); int t; long long x, y; cin >> t; while (t--) { cin >> x >> y; cout source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/1011.cpp basic-algo-lec.. 공감수 0 댓글수 1 2024. 10. 10.
[BOJ] 2482번 : 색상환 1. problem : https://www.acmicpc.net/problem/2482 2. solution 1 :#include using namespace std;int n, k; const int val = 1004;const int mod = 1e9 + 3;int d[val][val]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; if (k == 1) { cout source code 참고 : https://akim9905.tistory.com/71 [백준] 2482번 색상환[적용한 알고리즘] DP [아이디어] 1번과 N번이 둘 다 색칠되는 경우를 제외하고는, 나머지 경우는 선형으로 생각해줘도 된다. dp[N].. 공감수 0 댓글수 0 2024. 10. 8.
[BOJ] 11660번 : 구간 합 구하기 5 1. problem : https://www.acmicpc.net/problem/11660 2. solution 1 :#include using namespace std;const int val = 1030; int board[val][val];int d[val][val];int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for (int i = 1; i > board[i][j]; } for (int i = 1; i > x1 >> y1 >> x2 >> y2; int ans = d[x2][y2] - d[x2][y1 - 1] - d[x1 - 1][y2] + d[x1 - 1][y1 - 1]; cout dp를.. 공감수 0 댓글수 0 2024. 10. 7.
[BOJ] 9657번 : 돌 게임 3 1. problem : https://www.acmicpc.net/problem/9657 2. solution 1 :#include using namespace std;vector winners = { "SK","CY" };int n; vector rocks = { 1,3,4 }; int d[1005]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; d[1] = 0, d[2] = 1, d[3] = 0, d[4] = 0; for (int i = 5; i source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/9657.c.. 공감수 2 댓글수 1 2024. 10. 6.
[BOJ] 1520번 : 내리막 길 1. problem : https://www.acmicpc.net/problem/1520 2. solution 1 :#include using namespace std;int dx[4] = { 0,1,0,-1 };int dy[4] = { 1,0,-1,0 }; int n, m; int a[505][505], d[505][505]; int dp(int x, int y) { if (d[x][y] != -1) return d[x][y]; if (x == n - 1 && y == m - 1) return 1; int& ret = d[x][y]; ret = 0; for (int dir = 0; dir = n || ny = m) continue; if (a[x][y] > a[nx][ny]) ret += dp(.. 공감수 1 댓글수 0 2024. 10. 5.
[BOJ] 1476번 : 날짜 계산 1. problem : https://www.acmicpc.net/problem/1476 2. solution 1:#include using namespace std;int e, s, m; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}int lcm(int a, int b) { return a / gcd(a, b) * b;}int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> e >> s >> m; e--, s--, m--; int i = e; while (i % 28 != s) i += 15; int l = lcm(15, 28); while (i % 19 != m.. 공감수 0 댓글수 0 2024. 10. 4.
[BOJ] 2133번: 타일 채우기 1. problem : https://www.acmicpc.net/problem/2133 2. solution 1 :#include using namespace std;int d[33];int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; d[0] = 1, d[2] = 3; for (int i = 3; i = 0; j -= 2) { d[i] += d[j] * 2; } } cout source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2133.cpp basic-algo-lecture/0x10/solutions.. 공감수 0 댓글수 0 2024. 10. 3.
[BOJ] 9613번 : GCD 합 1. problem : https://www.acmicpc.net/problem/9613 2. solution 1 :#include using namespace std;int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}int main(void) { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; long long ans = 0; int a[105]; for (int i = 0; i > a[i]; for (int i = 0; i gcd를 직접 구현하여, 문제를 풀었다. ans는 100억이 될 수 있기 때문에, l.. 공감수 0 댓글수 0 2024. 10. 3.
[BOJ] 2294번 : 동전 2 1. problem : https://www.acmicpc.net/problem/2294 2. solution 1 :#include using namespace std;const int val = 10005;int coins[val]; int d[val];int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; for (int i = 1; i > coins[i]; d[0] = 0; for (int i = 1; i i) continue; if (d[i-coins[c]] == 10001) continue; d[i] = min(d[i], d[i - coins[c]] + 1); } } if (d[k] == 1.. 공감수 0 댓글수 0 2024. 10. 3.
[BOJ] 1676번 : 팩토리얼 0의 개수 1. problem : https://www.acmicpc.net/problem/1676 2. solution 1 :#include using namespace std;int n; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; int cnt = 0; for (int i = 5; i 0이 생기기 위해서는 10이 곱해져야 한다. 10은 2 * 5로, 2와 5의 배수를 찾으면 된다. 하지만, 2의 배수보다 5의 배수가 적기 때문에, 5의 배수의 개수를 세면 된다. 이때, 5의 제곱수는 5의 개수가 제곱승만큼 존재하게 된다. 예를 들어, 5^2은 5가 2개 존재한다. 따라서, 5의 배수, 25의 배수 그리고 125의 배수를 차례차례 더해줘야 .. 공감수 0 댓글수 0 2024. 10. 2.
[BOJ] 4883번 : 삼각 그래프 1. problem : https://www.acmicpc.net/problem/4883 2. solution 1 :#include using namespace std;const int val = 100005;int d[val][4]; int a[val][4];int main(void) { ios::sync_with_stdio(0); cin.tie(0); int t = 0; while (true) { t++; int n; cin >> n; if (n == 0) return 0; for (int i = 1; i > a[i][j]; } d[1][1] = INT_MAX; d[1][2] = a[1][2]; d[1][3] = a[1][2] + a[1][3]; for (int i = 2;.. 공감수 0 댓글수 0 2024. 10. 2.
[BOJ] 4948번 : 베르트랑 공준 1. problem : https://www.acmicpc.net/problem/4948 2. solution 1:#include using namespace std;const int val = 123456 * 2;vector eratos(int a) { vector primes; vector nums(a + 1, true); nums[1] = false; for (int i = 2; i * i primes = eratos(val); while (true) { int n; cin >> n; if (n == 0) return 0; int cnt = 0; for (auto p : primes) { if (n 에라토스테네스의 체를 이용해 풀었다. 공식이 기억나지 않아, 저번에 작성했던.. 공감수 0 댓글수 0 2024. 10. 1.
[BOJ] 1788번 : 피보나치 수의 확장 1. problem : https://www.acmicpc.net/problem/1788 2. solution 1 :#include using namespace std;int n;const int mod = 1000000000;const int val = 1000005;int d[val]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; d[1] = 1; for (int i = 2; i dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 1. 테이블을 정의한다. d[i] = i번째 피보나치 수 2. 점화식을 작성한다. d[i] = d [i-1] + d [i-2] 3. 초기값을 설정한다. d[0] = 0, d [1] = 1n이 음.. 공감수 0 댓글수 1 2024. 10. 1.
[BOJ] 1193번 : 분수찾기 1. problem : https://www.acmicpc.net/problem/1193 2. solution 1 :#include using namespace std;int x; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> x; int n = 0; while ((n * (n + 1) / 2) 1~n까지의 자연수합으로 n을 결정한 다음, 규칙을 이용해서 diff를 더하거나 빼줬다. 3. solution 2 :// Authored by : SciEm// Co-authored by : -// http://boj.kr/4786afbccbb148098938f248823abd35#include using namespace std;int main() .. 공감수 0 댓글수 0 2024. 10. 1.
[BOJ] 1904번 : 01타일 1. problem : https://www.acmicpc.net/problem/1904 2. solution 1:#include using namespace std;const int mod = 15746; int n; int d[1000005]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; d[1] = 1, d[2] = 2; for (int i = 3; i dp를 이용해 풀었다. 따라서, 세가지 스텝을 따른다. 1. 테이블을 정의한다. d[i] = i자리를 만드는데 필요한 경우의 수2. 점화식을 작성한다. d[i] = d[i-1] + d[i-2] 3. 초기값을 설정한다. d[1] = 1, d[2] = 2 공감수 0 댓글수 0 2024. 10. 1.
[BOJ] 2293번 : 동전 1 1. problem : https://www.acmicpc.net/problem/2293 2. solution 1 :#include using namespace std;int n, k; int a[105];int d[10005]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 0; i > a[i]; d[0] = 1; for (int i = 0; i source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2293.cpp basic-algo-lecture/0x10/solutions/22.. 공감수 0 댓글수 0 2024. 9. 30.
[BOJ] 2960번 : 에라토스테네스의 체 1. problem : https://www.acmicpc.net/problem/2960 2. solution 1 :#include using namespace std;int n, k;int board[1005]; vector ans;int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 2; i 에라토스테네스의 체를 이용해 풀었다. 좀 더 효율적인 방법이 있을 것 같다. 3. solution 2 :// Authored by : jihwan0123// Co-authored by : -// http://boj.kr/c980507acdc34d5ea79e397129f664c5#include using namespa.. 공감수 0 댓글수 1 2024. 9. 30.
[BOJ] 11057번 : 오르막 수 1. problem : https://www.acmicpc.net/problem/11057 2. solution 1 :#include using namespace std;int n; int d[1003][10];int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/11057.cpp basic-algo-lecture/0x10/solutions/11057.cpp at master · encrypted-def/basic-algo-lecture바.. 공감수 2 댓글수 1 2024. 9. 29.
[BOJ] 9465번 : 스티커 1. problem : https://www.acmicpc.net/problem/9465 2. solution 1 : #include using namespace std;const int val = 100005;int a[3][val];int main(void) { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n; int d[2][3][2] = { 0 }; cin >> n; for (int i = 1; i > a[i][j]; } for (int i = 1; i dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 1. 테이블을 정의한다. d [i][j][k] --> i번째 열, j번째 행을 k== .. 공감수 0 댓글수 0 2024. 9. 27.
[BOJ] 4796번 : 캠핑 1. problem : https://www.acmicpc.net/problem/4796 2. solution 1 :#include using namespace std;int main(void) { ios::sync_with_stdio(0); cin.tie(0); int i = 0; while (true) { i++; long long l, p, v; cin >> l >> p >> v; if (l == 0 && p == 0 && v == 0) return 0; long long ans = 0; long long div = v / p; ans += div * l; if (v - div * p > l) ans += l; else ans += v - div * p; cout p를 이용해 몫을.. 공감수 3 댓글수 1 2024. 9. 26.
[BOJ] 15894번 : 수학은 체육과목 입니다 1. problem : https://www.acmicpc.net/problem/15894 2. solution 1 :#include using namespace std;long long n;int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; cout 옆면을 옆으로 밀어버리고, 밑면은 밑으로 밀어버리고, 윗면은 위로 밀어버리면, 정사각형이라고 생각할 수 있다. 설명참조 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/15894.cpp basic-algo-lecture/0x12/solutions/15894.cpp at master · encryp.. 공감수 2 댓글수 1 2024. 9. 26.
[BOJ] 11052번 : 카드 구매하기 1. problem : https://www.acmicpc.net/problem/11052 2. solution 1 :#include using namespace std;int t; int a[1005]; int d[1005]; // i일때 최댓값 int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> t; for (int i = 1; i > a[i]; d[0] = 0; for (int i = 1; i dp를 이용해 풀었다. 따라서 세 가지 스텝을 따른다. 1. 테이블을 정의한다. d[i] = i개를 살 때, 최대 금액이다. 2. 점화식을 작성한다. d[i] = max(d [i] , d [i-j] + a [j])) 3. 초기값을 설정한다. d[0].. 공감수 0 댓글수 0 2024. 9. 26.
[BOJ] 2302번 : 극장 좌석 1. problem : https://www.acmicpc.net/problem/2302 2. solution 1 :#include using namespace std;int d[42]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); d[0] = 1, d[1] = 1, d[2] = 2; for (int i = 3; i > n; cin >> m; int ans = 1; int start_idx = 1; while (m--) { int x; cin >> x; ans *= d[x - start_idx]; start_idx = x + 1; } ans *= d[n - start_idx + 1]; cout dp를 이용해 풀었다. 따라서, 세 가지 스텝.. 공감수 0 댓글수 0 2024. 9. 25.
[BOJ] 6064번 : 카잉 달력 1. problem : https://www.acmicpc.net/problem/6064 2. solution 1 :#include using namespace std;int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}int lcm(int a, int b) { return a / gcd(a, b) * b;}int solve(int m, int n, int x, int y) { if (x == m) x = 0; if (y == n) y = 0; int l = lcm(m, n); for (int i = x; i > t; while (t--) { cin >> m >> n >> x >> y; cout source code 출처 .. 공감수 0 댓글수 0 2024. 9. 25.
[BOJ] 11051번 : 이항 계수 2 1. problem : https://www.acmicpc.net/problem/11051 2. solution 1 :#include using namespace std;int n, k; int d[1005][1005]; const int val = 10007;int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 0; i 조합의 성질을 이용하여, nCk = n-1Ck-1 + n-1Ck 풀었다. 이 성질을 이용하여 dp를 사용했다. 따라서 세 가지 스텝을 따른다. 1. 테이블을 정의한다. d[i][j]는 iCj를 나타낸다. 2. 점화식을 작성한다. 조합의 성질을 이용하여, d [i][j] = d [i-1][j-1.. 공감수 0 댓글수 0 2024. 9. 25.
[BOJ] 11050번 : 이항 계수 1 1. problem : https://www.acmicpc.net/problem/11050 2. solution 1 :#include using namespace std;int n, k; int factorial(int a) { if (a == 0 || a == 1) return 1; return a * factorial(a - 1);}int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; int ans = factorial(n) / (factorial(n - k) * factorial(k)); cout factorial 함수를 재귀적으로 구현했다. 3. solution 2 :// Authored by : Baaaaaaaaaaar.. 공감수 0 댓글수 0 2024. 9. 24.
[BOJ] 15988번 : 1,2,3 더하기 3 1. problem : https://www.acmicpc.net/problem/15988 2. solution 1:#include using namespace std;typedef long long ll;const int val = 1000000009;int n; ll d[1000005]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); d[0] = 1, d[1] = 1, d[2] = 2; for (int i = 3; i > n; while (n--) { int x; cin >> x; cout dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 첫 번째, 테이블을 정의한다. d [i] = i일 때 경우의 수 두 번째, 점화식을 작성한다... 공감수 0 댓글수 0 2024. 9. 23.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.