DP
-
[백준] 2193번 이친수알고리즘/백준 2021. 8. 23. 17:12
문제 링크 풀이 다섯 번째 항까지 직접 경우의 수를 세어 보면 피보나치 수열과 동일한 규칙을 찾을 수 있습니다. 90번째 항까지 구해야 하는데, int형은 표현 범위를 초과하기 때문에 점화식은 long long으로 만들어줍니다. 규칙을 이렇게도 생각해볼 수 있습니다. 다섯 자리라고 할 때 10xxx0인 경우와 10xx01인 경우입니다. 0으로 끝날 때 d[n-1]과 01으로 끝나는 경우인 d[n-2]를 더해서 d[n]을 구하는 것입니다. d[n] = d[n-1] + d[n-2]이고 초기값만 잘 세팅해주면 됩니다. 코드 #include int main() { int N; scanf("%d", &N); long long d[90] = {}; d[0] = 1; d[1] = 1; for (int i = 2; i..
-
[백준] 2156번 포도주 시식알고리즘/백준 2021. 8. 23. 16:25
문제 링크 풀이 계단 오르기 문제와 비슷한데 다릅니다. 계단 오르기 문제는 반드시 마지막 계단을 밟아야 한다는 조건이 있었지만 이 문제는 아닙니다. 점화식을 구할 때 d[i]가 i번째 와인인 w[i]을 반드시 선택할 필요는 없다는 의미입니다. 예를 들어 8 5 4 2에서 3개를 선택하는 연속합의 최대값을 구할 때 마지막 숫자인 2를 반드시 포함해야 한다면 5+4+2=11이지만 마지막을 선택하지 않아도 된다면 8+5+4=17입니다. d[i]를 구할 때 w[i]를 포함하는 경우에서의 최대값을 구하고 나서 d[i-1]과도 비교를 해야 하는 이유입니다. 코드 #include int max(int a, int b) { return a > b ? a : b; } int main() { const int MAX = ..
-
[백준] 1912번 연속합알고리즘/백준 2021. 8. 22. 23:48
문제 링크 풀이 점화식 d[i]는 i번째 요소까지의 연속합의 최대 값입니다. 문제에서 수는 한 개 이상 선택해야 한다고 했으므로 d[i-1]번째 수와 arr[i]를 더했을 때의 값이 arr[i]의 값보다 작다면 i번째 요소인 arr[i] 자체가 연속합의 최대 값이 됩니다. 그러므로 다음과 같은 점화식을 세울 수 있습니다. answer의 초기 값이 -100000000인 이유는 요소에 음수 값이 있을 수 있기 때문입니다. d[i] = max(d[i-1] + arr[i], arr[i]) 코드 #include int max(int a, int b) { return a > b ? a : b; } int main() { int N; scanf("%d", &N); int d[100001] = {}; int arr[1..
-
[백준] 11053번 가장 긴 증가하는 부분 수열알고리즘/백준 2021. 8. 19. 20:12
문제 링크 풀이 자세한 설명보다는 개념적으로 설명하겠습니다. { 1, 2, 1, 2, 3, 5, 4 }라는 수열로 예를 들겠습니다. d[i]는 i번째 요소를 마지막 수로 하는, 증가하는 수열의 길이로 하겠습니다. 인덱스는 1부터 하겠습니다. d[1]은 1이고 d[2]는 2입니다. d[3]은 1이고요 d[4]는 2, d[5]는 3, d[6]은 4, d[7]은 4입니다. d[i]는 i번째 요소보다 작은 요소 중에서 가장 큰 요소를 마지막 값으로 하는 수열의 길이에서 1을 더한 값이 됩니다. 예를 들어, 다섯 번째 요소가 3인데요, 이는 3보다 작은 수 중에 가장 큰 수인 2를 마지막 요소로 하는 수열의 길이에서 1을 더한 값이라는 거죠. 그니까 3보다 작은 d[i]의 최대값을 찾아 1을 더하면 됩니다. 코드..
-
[백준] 1932번 정수 삼각형알고리즘/백준 2021. 8. 18. 19:17
문제 링크 풀이 이차원 배열도 일차원 배열처럼 연속된 메모리에 지나지 않지만 개발자가 작업할 때는 직관적으로 접근할 수 있어서 편합니다. 이 문제를 이차원 배열로 풀면 조금 편합니다. 예제로 주어진 입력값을 이차원 배열을 이용해 다음처럼 할 수 있습니다. 이 배열은 점화식을 위한 이차원 배열이며 dp[3][2]는 [3][2] 위치까지 합산된 최대값을 표현합니다. 즉 dp[2][1]과 dp[2][2]를 비교해서 더 큰 값을 [3][2]의 좌표의 값과 더해서 dp[3][2]를 갱신하면 됩니다. 점화식은 다음과 같습니다. d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j] 반복문 사용을 최소화하기 위해 triangle 이차원 배열을 선언하지 않고 일차원 배열을 하..
-
[백준] 2579번 계단 오르기알고리즘/백준 2021. 8. 18. 17:23
문제 링크 풀이 계단을 연속해서 세 계단을 오를 수 없고 연속해서 두 번 혹은 한 계단을 건너뛸 수 있습니다. n번째 계단은 반드시 밟아야 합니다. 즉 n-3, n-2, n 순서대로 밟거나 n-3, n-1, n의 두 가지 경우를 점화식으로 도출할 수 있습니다. 이 중에서 큰 값을 구하면 되는 것이죠. 앞의 순서는 d[n-2] + s[n]이며 뒤는 d[n-3] + s[n-1] + s[n]입니다. 코드 #include #include int main() { int N; scanf("%d", &N); int s[301] = { 0 }; int d[301] = { 0 }; for (int i = 1; i
-
[백준] 1149번 RGB 거리알고리즘/백준 2021. 8. 18. 14:53
문제 링크 풀이 점화식 d[N]은 N번째 집까지 칠했을 때의 최소 비용으로 정의합니다. 조금 더 정확히 표현하면 N번째 집을 빨간색으로 칠할 때, 초록색으로 칠할 때, 파란색으로 칠할 때의 각 경우의 최소 비용입니다. N-1번째 항에는 이미 N-1번째 집을 빨간색, 초록색, 파란색으로 칠했을 경우의 최소 비용이 이미 구해져 있다는 의미이므로 이전 항의 각 비용 값에 N번째에 칠하고 싶은 색의 비용을 더하면 됩니다. 점화식은 다음과 같습니다. d[N][0] = min(d[N-1][1], d[N-1][2]) + cost[0] d[N][1] = min(d[N-1][0], d[N-1][2]) + cost[1] d[N][2] = min(d[N-1][0], d[N-1][1]) + cost[2] answer = mi..