https://www.acmicpc.net/problem/2629 풀이: 양팔저울에 추를 매달아 구할 수 있는 무게를 알아내는 문제 양팔저울에 한 곳에 놓았을 때, 양쪽에 서로 따로 놓았을 때 두 가지의 경우가 있다. 이 때 같이놓으면 + 따로 놓은것은 -로 놓고 배열에 저장한다. 구슬의 무게에 맞는 배열의 값이 1이면 구할 수 있고, 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 #include <iostream>#include <map>#include <vector>using namespace std; map<int, int> a; vector<int> b; int main(void) { int n, temp, k, size; cin >> n; for (int i = 0; i < n; i++) { cin >> temp; map<int, int>::iterator iter; size = a.

https://www.acmicpc.net/problem/2698 풀이: a[n][k][0] : 크기가 n이고 인접비트의 수가 k이며, 끝에 비트가 0인 수 a[n][k][1] : 크기가 n이고 인접비트의 수가 k이며, 끝에 비트가 1인 수 a[n][k][0] = a[n - 1][k][0] + a[n - 1][k][1] a[n][k][1] = a[n - 1][k][0] + a[n - 1][k - 1][1] 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream>using namespace std; int a[102][102][2] = { 0 }; int main(void) { int T, n, k; int cnt = 2; cin >> T; a[1][0][1] = 1; a[1][0][0] = 1; for (int i = 0; i < T; i++) { cin >> n >> k; for (int t = cnt; t < n + 1; t++) { for (int y = 0; y < t; y++) { a[t][y][0] = a[t - 1][y][0] + a[t - 1][y][1]; a[t][y][1] = a[t - 1][y][0] + a[t - 1][y - 1][1]; } } cout << a[n][k][0] + a[n][k][1] << endl; cnt = n; } return 0; }

https://www.acmicpc.net/problem/1793 풀이: 11727 2XN 타일링2 DP는 링크와 같으므로 링크를 참고 링크의 코드와 다르게 int 보다 큰 값을 출력해야하므로 어려움이 있다. vector를 사용하여 int를 한자리수 씩 계산하는 방법으로 풀었다. 만약 자릿수의 값이 10보다 커지면 다음 자릿수의 값을 그만큼 올려주는 식으로 풀었다. 코드: 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 #include <iostream>#include <vector>using namespace std; vector<int> a[251]; int main(void) { int n, temp; int cnt = 3; a[0].

https://www.acmicpc.net/problem/2718 풀이: a[t] 는 4 x t 크기의 타일을 채울 수 있는 경우의 수 a[t] = a[t - 1] + a[t - 2] * 5 + a[t - 3] - a[t - 4]; 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream>#include <algorithm>using namespace std; int a[30] = { 1,5,11,36 }; int main(void) { int T,n,cnt; cnt = 5; cin >> T; for (int i = 0; i < T; i++) { cin >> n; if (a[n - 1] == 0) for (int t = cnt-1; t < n; t++) { a[t] = a[t - 1] + a[t - 2] * 5 + a[t - 3] - a[t - 4]; } cout << a[n - 1] << endl; cnt = max(cnt, n); } return 0; }

https://www.acmicpc.net/problem/11722 풀이: 11053 가장 긴 증가하는 부분 수열의 문제와 똑같으므로 링크를 참고 코드: 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 #include <iostream>#include <algorithm>using namespace std; int main(void) { int n, temp; cin >> n; int a[1001] = { 0 }; int b[1001]; for (int i = 0; i < n; i++) { cin >> a[i]; b[i] = 1; } for (int i = 0; i < n; i++) { temp = 0; for (int t = 0; t <= i; t++) { if (a[i] < a[i - t]) temp = max(b[i - t], temp); } b[i] += temp; } for (int i = 0; i < n; i++) { temp = max(b[i], temp); } cout << temp << endl; return 0; }

https://www.acmicpc.net/problem/4883 풀이: N X 3 행렬에서 맨 위 중앙에서 출발하여 맨 아래 중앙까지 가는 경로 중 가장 최소 비용을 찾는 문제 각 i행의 1,2,3번째 열의 각각 최소비용은 i-1 번째 행에서의 최소 비용을 더해준 값이다. 맨 마지막 행의 2번째 열을 출력한다. 0이 출력되면 끝나므로 if문으로 while 문을 빠져나갈 수 있게한다. 하나의 테스트케이스마다 숫자를 출력해야하므로 count 값을 각 케이스마다 ++해준다. 코드: 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 #include <iostream>#include <algorithm>using namespace std; int a[100005][3], b[100005][3]; int main(void) { int count = 1; while (true) { int n, temp, temp2; cin >> n; if (n == 0) break; for (int i = 0; i < n; i++) { for (int t = 0; t < 3; t++) { cin >> a[i][t]; b[i][t] = a[i][t]; } } b[0][2] += b[0][1]; b[1][0] += b[0][1]; b[1][1] += min(min(b[0][1],b[1][0]), b[0][2]); b[1][2] += min(min(b[1][1], b[0][1]), b[0][2]); for (int i = 2; i < n; i++) { for (int t = 0; t < 3; t++) { if (t == 0) b[i][t] += min(b[i - 1][t], b[i - 1][t + 1]); else if (t == 1) b[i][t] += min(min(b[i - 1][t], b[i - 1][t + 1]), min(b[i - 1][t - 1], b[i][t - 1])); else if (t == 2) b[i][t] += min(min(b[i - 1][t - 1], b[i - 1][t]), b[i][t - 1]); } } cout << count << ".