C++ Algorithm/백준 알고리즘 문제 풀이
동적 계획법 기초
3영2
2019. 4. 8. 15:11
반응형
1932번 문제 : 피보나치 함수
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <iostream> using namespace std; struct MyFibo { int value; int zeroCount; int oneCount; }; MyFibo fib[50]; int GetFibo(int n) { if (n == 0) { fib[0].value = 0; fib[0].zeroCount = 1; return 0; } else if (n == 1) { fib[1].value = 1; fib[1].oneCount = 1; return 1; } if (fib[n].value != 0) { return fib[n].value; } else { fib[n].value = GetFibo(n - 1) + GetFibo(n - 2); fib[n].zeroCount = fib[n - 1].zeroCount + fib[n - 2].zeroCount; fib[n].oneCount = fib[n - 1].oneCount + fib[n - 2].oneCount; } } int main() { int inp; cin >> inp; while (inp > 0) { int a; cin >> a; zeroCounter = 0; oneCounter = 0; GetFibo(a); cout << fib[a].zeroCount << " " << fib[a].oneCount << endl; inp--; } return 0; } | cs |
1149번 문제 : RGB거리
https://www.acmicpc.net/problem/1149
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <iostream> #include <algorithm> using namespace std; int DP[1001][4] = { 0 }; int main() { int inp; cin >> inp; for (int i = 1; i <= inp; i++) { int r, g, b; cin >> r >> g >> b; DP[i][1] = r; DP[i][2] = g; DP[i][3] = b; } for (int i = 2; i <= inp; i++) { for (int j = 1; j <= 3; j++) { if (j == 1) DP[i][j] += min(DP[i - 1][2], DP[i - 1][3]); else if (j == 2) DP[i][j] += min(DP[i - 1][1], DP[i - 1][3]); else if (j == 3) DP[i][j] += min(DP[i - 1][1], DP[i - 1][2]); } } int min = DP[inp][1]; for (int j = 1; j <= 3; j++) { if (DP[inp][j] < min) min = DP[inp][j]; } cout << min << endl; return 0; } | cs |
1932번 문제 : 정수 삼각형
https://www.acmicpc.net/problem/1932
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <iostream> #include <algorithm> using namespace std; int DP[501][501] = { 0 }; int main() { int size; cin >> size; for (int i = 1; i <= size; i++) { for (int j = 1; j <= i; j++) { int inp; cin >> inp; DP[i][j] = inp; } } for (int i = 2; i <= size; i++) { for (int j = 1; j <= i; j++) { if (j == 1) { DP[i][j] += DP[i - 1][j]; } else if (j == i) { DP[i][j] += DP[i - 1][j - 1]; } else { DP[i][j] += max(DP[i - 1][j - 1], DP[i - 1][j]); } } } int max = 0; for (int j = 1; j <= size; j++) { if (DP[size][j] > max) max = DP[size][j]; } cout << max << endl; return 0; } | cs |
메모:
-위쪽부터 누적 최대값을 취하는 방식으로 풀어야함
-양쪽끝 (위 코드에서는 j =1 또는 j =i)일때는 받을 수 있는 값은 하나 밖에 없음
-가운데에 있는 숫자들은 양쪽에서 값을 받을 수 있음
1463번 문제 : 1로 만들기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include <iostream> #include <vector> #include <algorithm> using namespace std; int arr[1000001] = { 0 }; int GetValue(int num) { if (num == 0 || num == 1) { arr[num] = 0; return 0; } else if (num == 2 || num == 3) { arr[num] = 1; return 1; } if (arr[num] != 0) return arr[num]; else { arr[num] = arr[num - 1] + 1; if (num % 2 == 0) { arr[num] = min(arr[num], arr[num / 2] + 1); } if (num % 3 == 0) { arr[num] = min(arr[num], arr[num / 3] + 1); } return arr[num]; } } int main() { int inp; cin >> inp; for (int i = 1; i <= inp; i++) { GetValue(i); } cout << arr[inp] << endl; return 0; } | cs |
메모:
-3부터 나뉘어지면 무조건 취소값이라고 생각하면 안됨
-그래서 그 전의 수와 비교하면서 루프를 돌아야함
9461번 문제 : 파도반 수열
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <iostream> #include <vector> using namespace std; signed long long value[101] = { 0,1,1,1,2,2,3,4,5,7 }; vector<signed long long> result; int GetValue(int num) { if (num <= 8) return value[num]; else { if (value[num] != 0) return value[num]; else { value[num] = value[num - 1] + value[num - 5]; return value[num]; } } } int main() { int t; cin >> t; for (int i = 0; i <= 100; i++) { GetValue(i); } while (t > 0) { int inp; cin >> inp; result.push_back(value[inp]); t--; } for (auto i : result) cout << i << endl; return 0; } | cs |
메모:
-i가 80정도 이상이면 long long 범위를 벗어나 답을 못구함...
반응형