본문 바로가기

DP24

BOJ 12865: 평범한 배낭 https://www.acmicpc.net/problem/12865 코드를 짰는데 중복으로 물건을 고를 수 있게 짜서 이걸 어쩌냐 하다가 그냥 포기하고 다른 분의 풀이를 봤다. 내가 다이나믹 프로그래밍이라고 하면 뭔가 생각이 점화식을 어떻게 짜는지에만 몰두하느라 생각을 우연하게 하지 못한 것이 패착인 것 같다. 나이브한 솔루션인 전체 탐색에 메모이제이션을 이용해서 시간을 줄이는 방식이라고 보면 된다. 나이브한 솔루션은 아이템 i를 뽑냐, 뽑지 않냐로 경우의 수를 나누어서 N번째 (1부터 시작했을 때) 아이템까지 확인하는 방식이다. 정말 간단하지 않은가..?? 좀 더 다양한 DP 문제를 풀면서 생각의 유연성을 길러야 할 것 같다는 반성으로 마무리하겠다. 2022. 5. 21.
[BOJ] 1699번: 제곱수의 합 1699번: 제곱수의 합 해법 DP, 동전2 문제와 굉장히 유사하다. 분명히 정올 준비를 하면서 이 문제를 풀어 봤음에도 불구하고 처음에는 n보다 작으면서 가장 가까운 제곱수를 빼주는 것으로 생각했는데 그렇게 하니까 32 = 16 + 16같은 반례에 막혔다.(당연하다... ㅠ) 그래서 다시 생각한 것이 제곱수들의 리스트가 주어질 때 i를 범위 내의 제곱수들로 뺀 수의 최소 구성 개수 중에서 가장 작은 것을 고르는 것으로 생각했다.(= min(D[i - sqrt_list[j]]) ) 그래서 나온 점화식은 다음과 같다. int Min = dp[i - sqrt_list[0]]; for (int j = 1; j 0) return dp[n]; int idx = find_close(n); dp[n] = 1 + st.. 2018. 8. 30.
[BOJ] 9465번: 스티커 9465번: 스티커 해법 처음 내가 접근했던 방법은 그냥 무식하게 대각선으로만 생각하고 풀었다. 그래서 당연히 틀렸고 친구와 다른 분들의 도움을 받아서 이 문제를 풀게 됐다. 우선 이 문제는 DP이고 DP식은 dp[i][j]: i열,j행까지의 스티커의 최대값이다. 하나를 선택하면 상하좌우를 선택하지 못하기 때문에 기본적으로 이동은 대각선으로만 가능하다. 그래서 DP식을 대각선쪽만 생각해서 짜면 절대 안된다. 이렇게 한다면 250이 최대가 되어서 정답인 260이 아니게 된다. 즉 한 칸을 건너뛰어야 한다. 그러면 두 칸을 건너뛰는 것은 어떨까..? 결론부터 말하자면 손해다. 두 칸을 뛰게 되면 한 칸씩 대각선 건너는 것과 같은 지점을 가지만 거치는 것은 더 적으므로 항상 손해일 수 밖에 없다. 그래서 점화.. 2018. 8. 30.
[BOJ] 2698번: 인접한 비트의 개수 https://www.acmicpc.net/problem/2698 D[n][k][lb]: 길이가 n이고 연속된 비트가 k개이면서 마지막 비트가 lb(0 또는 1)인 수열의 개수 처음에는 D[n][k]으로만 점화식을 세워보려고 했는데 끄적끄적하다 보니 결국에는 마지막 비트와 관계가 있어서 어쩔 수 없이 사용하게 되었다. 마지막 비트가 0일 때 D[n][k][lb] = D[n - 1][k][0] + D[n - 1][k][1] 마지막 비트가 0인데 길이는 n이고 연속된 비트가 k인 수열의 개수는 길이 n-1짜리에서 마지막 비트가 0, 1인 두 개의 수를 합치면 된다. ex) 11100, 01110 -> 1110에서 0하나 붙이면 되고, 0111에서 0하나 붙이면 된다. 마지막 비트가 1일 때 D[n][k][l.. 2018. 8. 7.
[BOJ] 2775번: 부녀회장이 될테야 https://www.acmicpc.net/problem/2775 D[i][j]: i층 j호의 거주민 수 D[0][i] = i D[i][j] = D[i - 1][for k: 1...j] #include int D[15][15]; int main() { int T; for (int i = 1; i 2018. 8. 4.
[BOJ] 9095번: 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 dp[k]: k를 1,2,3의 합으로 나타낼 수 있는 경우의 수 dp[k] = dp[k - 1] + dp[k - 2] + dp[k - 3] k - 1에서 +1을 해서 k를 만들 수 있고 나머지 k-2,k-3도 같은 방식으로 만들 수 있다. #include int memo[11]; int f(int k) { if (memo[k]) return memo[k]; return memo[k] = f(k - 1) + f(k - 2) + f(k - 3); } int main() { int n; scanf("%d", &n); memo[1] = 1; memo[2] = 2; memo[3] = 4; while (n--) { int input; scanf("%.. 2018. 7. 27.
[BOJ] 14650번: 걷다보니 신천역 삼 (Small) 14650번: 걷다보니 신천역 삼 (Small) 14650번: 걷다보니 신천역 삼 (Small) 욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 금강삼도 식후경, 걷다보니 신천역 삼, 그리고 특히 일이삼을 좋아한다. 그래서 욱제는 3을 가지고 놀아보기로 했삼. 3개 숫자(0, 1, 2)만 가지고 N자리 3의 배수를 만들어 보삼. 만드는 배수는 자연수 이삼. 0으로 시작하는 수는 만들 수 없는 수 이삼. 3의 배수가 몇 개나 나올 수 있삼? www.acmicpc.net N의 최대 크기가 9이기 때문에 brute force를 해도 되지만 간단한 dp 문제로 풀 수 있다. 참고: 14651번: 걷다보니 신천역 삼.. 2018. 7. 19.
[BOJ] 14651번: 걷다보니 신천역 삼 (Large) 14651번: 걷다보니 신천역 삼 (Large) 이기 때문에 처음에는 코드를 이렇게 짰다. #include long long n, dp[33334][3]; const int R = 1e9 + 9; int main() { scanf("%lld", &n); dp[2][0] = 0, dp[2][1] = dp[2][2] = 1; for (int i = 3; i 2018. 7. 19.
[BOJ] 11048번: 이동하기 11048번: 이동하기 풀이 간단히 바로 생각나는 점화식은 dp[i][j]=max(dp[i−1][j],dp[i−1][j−1],dp[i][j−1])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j-1], dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i−1][j−1],dp[i][j−1])인데 캔디 개수로 음수가 나올리가 없으므로 dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]을 도는 것은 사치다. 최대한 많이 얻어야 좋은 건데 바로 한 단계를 건너뛰는 것은 엄연한 사치다. 그래서 dp[i][j]=max(dp[i−1][j],dp[i][j−1])dp[i][j] = max(dp[i - 1][j], dp[i][j-1])dp[i][j]=max(dp[i−.. 2018. 6. 4.
[BOJ] 1932번: 정수 삼각형 1932번: 정수 삼각형 풀이 현재 칸을 기준으로 이전 칸에서 좌, 우를 비교해서 최댓값을 계속 축적해주면 된다. 그리고 마지막 줄을 순회하면서 최댓값을 구하는 방법. 코드 예전에 짠 코드 #include const int MAX = 501; int N, max = -1, i, j; int v[MAX][MAX]; void input() { scanf("%d", &N); for (int i = 1; i 2018. 6. 4.
[BOJ] 11057번: 오르막 수 11057번: 오르막 수 풀이 우선 본 문제의 아이디어는 쉬운 계단 수에서 가져왔다. 굉장히 유사한 방법(거의 똑같다)으로 풀 수 있었다. D[i][j]는 길이가 i이고 끝자리 숫자가 j인 오르막 수 따라서 i - 1 길이, 끝자리 숫자가 현재 j보다 작은 오르막 수들의 경우의 수를 누적 시키면 된다. 코드 #include int n, D[1001][10]; const int div = 10007; int main() { scanf("%d", &n); for (int i = 0; i 2018. 6. 3.
[BOJ] 1010번: 다리 놓기 1010번: 다리 놓기 풀이 문제 읽을 때부터 뭔가 조합의 느낌이 났는데 조합이었다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래서 nCr을 구현해주면 된다. 코드 #include #include int n, r, D[31][31]; long long int nCr(int n, int r) { if (n == r || r == 0) return D[n][r] = 1; if (r == 1) return D[n][r] = n; if (D[n][r]) return D[n][r]; return D[n][r] = (nCr(n - 1, r - 1) + nCr(n - 1, r)); } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d %d", &n, &r); printf.. 2018. 6. 3.
[BOJ] 2163번: 초콜릿 자르기 2163번: 초콜릿 자르기 풀이 감이 안 잡혔는데 그냥 우리가 실제로 초콜릿을 쪼갤 때를 생각하면 된다. 보통 반으로 계속 쪼개지 않는가? 그걸 생각하며 관계식을 세우면 된다. 가로로 반으로 쪼갤 때 or 세로로 반으로 쪼갤 때 중 최솟값을 구하면 된다. 코드 #include #include int D[301][301], N, M; int f(int n, int m) { // 종료 조건 if (n == 1) return D[n][m] = m - 1; else if (m == 1) return D[n][m] = n - 1; return D[n][m] = std::min(n * f(1, m) + (n - 1), m * f(n, 1) + (m - 1)); } int main() { scanf("%d %d", .. 2018. 6. 2.
[BOJ] 11052번: 붕어빵 판매하기 11052번: 붕어빵 판매하기 풀이 D[i] = i개를 판매해서 얻을 수 있는 최대 이익 D[i] = D[i - k] + P[k] 중 최대값을 구하면 되는 간단한 문제다. i개 남은 거에서 k개를 선택한다면 i - k개 중 최대 이익 + k개 이익(P[k])를 더해주면 i개의 최대 이익이 되기 때문에 저런 관계식이 나오게 된다. 코드 #include #include int gN, P[1001], D[1001]; inline int Max(int a, int b) { return (a > b ? a : b); } int f(int n) { if (D[n] != -1) return D[n]; if (n == 0) return 0; for (int i = 1; i = 0) D[n] = Max(D[n], f(n.. 2018. 6. 2.
10844번: 쉬운 계단 수 10844번: 쉬운 계단 수 풀이 D[i][j]는 길이가 i이고 끝자리 숫자가 j인 계단 수 n=1일때의 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9이고 n=2 일때의 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, ··· 등이 있다. D[2][2]일 경우를 한 번 보자. 12, 32가 있는데 첫 자리 수는 끝자리 수인 2에서 ±1이다. 그래서 관계식이 D[i][j]=D[i−1][j+1]+D[i−1][j−1](j≠0∣j≠9)D[i][j] = D[i - 1][j + 1] + D[i - 1][j - 1](j \ne 0|j \ne 9)D[i][j]=D[i−1][j+1]+D[i−1][j−1](j≠0∣j≠9) 이렇게 나온다. j = 0일땐 D[i][j] = D[i - 1][j + .. 2018. 6. 1.

티스토리툴바