https://www.acmicpc.net/problem/9184 풀이: DP함수가 주어져 있으므로 메모이제이션을 하면된다. 단, a, b, c 의 최대 크기가 주어져있지않으므로 20이 넘어간 값은 생략하도록한다. -1, -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 #include <iostream> #include <string.h> using namespace std; int fuc[21][21][21]; int w(int a,int b,int c) { if (a <= 0 || b <= 0 || c <= 0) return 1; if (a > 20 || b > 20 || c > 20) return fuc[20][20][20] = w(20, 20, 20); if (fuc[a][b][c] > -1) return fuc[a][b][c]; if (a < b && b < c) return fuc[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c); return fuc[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1); } int main(void) { int a, b, c; memset(fuc, -1, sizeof(fuc)); while(true){ cin >> a >> b >> c; if (a == -1 && b == -1 && c == -1) break; cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl; } return 0; }

https://www.acmicpc.net/problem/9251 풀이: dp[a][b]를 1 ~ a번째 까지의 문자열과 1 ~ b 까지의 문자열로 이루어진 최장 공통 부분수열이라고 하자. a번째 문자와 b번째 문자가 같다면, dp[a - 1][b - 1] 에 1을 더해준다. 즉, dp[a][b] = dp[a - 1][b - 1] + 1 이 된다. a번째 문자와 b번째 문자가 다르다면, a번째 문자를 제거한 문자열과 b번째 문자를 제거한 문자열을 비교하여 최댓값을 받는다. 즉, dp[a][b] = max(dp[a - 1][b], dp[a][b - 1]) 이 된다.

https://www.acmicpc.net/problem/9322 풀이: 제 1 공개키에 각각에 단어들이 제 2 공개키에 어디에 있는지 확인한다. 제 1 공개키에 첫번째 단어부터 제 2 공개키에서의 위치에 있는 암호키를 출력한다. 코드: 사용언어 : Python 3 1 2 3 4 5 6 a,b,c=[],[],[] for i in range(int(input())): n=int(input()) a,b,c=input().split(),input().split(),input().split() for t in range(n): print(c[b.index(a[t])],end=" ")

+++ author = “jyukki” categories = [“백준”] tags = [“algorithm”, “C++”, “DP”] date = “2017-11-30” description = “algorithm” featured = "" featuredalt = "" featuredpath = “date” linktitle = "" title = “[백준]9465 스티커” +++ https://www.acmicpc.net/problem/9465 풀이: a[i][t] 는 i행 t열의 스티커를 골랐을 때 최대 점수 a[t][i] += max(a[(t + 1) % 2][i - 2], a[(t + 1) % 2][i - 1]) 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream>#include <algorithm>using namespace std; int a[2][100001] = { 0 }; int main(void) { int T,n; cin >> T; for (int y = 0; y < T; y++) { cin >> n; for (int t = 0; t < 2; t++) { for (int i = 0; i < n; i++) { cin >> a[t][i]; } } for (int i = 1; i < n; i++) { for (int t = 0; t < 2; t++) { a[t][i] += max(a[(t + 1) % 2][i - 2], a[(t + 1) % 2][i - 1]); } } cout << max(a[0][n - 1], a[1][n - 1]) << endl; } }

https://www.acmicpc.net/problem/9546 풀이: 처음 사람의 수 = 2^k - 1 코드: 사용언어 : Python 3 1 2 3 4 t=int(input()) for i in range(t): k=int(input()) print((2**k)-1)

https://www.acmicpc.net/problem/9550 풀이: 사탕개수를 최소 K개 만큼 주어야 하므로 각각의 사탕을 K로 나눈 몫을 모두 더한 값을 출력한다. 코드: 사용언어 : Python 3 1 2 3 4 5 6 7 8 T = int(input()) for i in range(T): cnt = 0 n,k = map(int,input().split(' ')) c = input().split(' ') for t in range(n): cnt += int(c[t]) // k print(cnt)