백준 1029번 그림 교환 - C++ 풀이
1. dp(curr, price, mask) = 현재 curr이 price원에 그림을 가지고 있고 지금까지 그림을 산 사람들이 mask일 때, 더 그림을 소유할 수 있는 사람 수의 최댓값 2. dp(curr, price, mask) = max(1, 1 + dp(next, nextPrice, newMask)) 1. dp(curr, price, mask) = 현재 curr이 price원에 그림을 가지고 있고 지금까지 그림을 산 사람들이 mask일 때, 더 그림을 소유할 수 있는 사람 수의 최댓값 dp(curr, price, mask)를 위와 같이 정의하자. 사람은 최대 15명, 가격은 최대 9원이므로 총 구해야 하는 dp값은 15*10*(2^15) 개. 2. dp(curr, price, mask) = max..
2022. 7. 3.
백준 2169번 로봇 조종하기 - C++ 풀이
1. dp(r, c, before): 이전 칸이 before이고 현재 (r, c)일 때, (N, M)으로 가면서 얻을 수 있는 가치의 최대 합 2. dp(r, c, before) = board[r][c] + max(dp(r+1, c, UP), dp(r, c-1, RIGHT), dp(r, c+1, LEFT)) 1. dp(r, c, before): 이전 칸이 before이고 현재 (r, c)일 때, (N, M)으로 가면서 얻을 수 있는 가치의 최대 합 dp(r, c, before)를 위와 같이 정의하자. 아래, 왼쪽, 오른쪽으로만 이동할 수 있으므로 before는 위, 왼쪽, 오른쪽 중 하나가 된다. 2. dp(r, c, before) = board[r][c] + max(dp(r+1, c, UP), dp(r..
2022. 6. 14.
백준 1701번 Cubeditor - C++(cpp) 풀이
1. dp(a, b): 가장 길게 일치하는 부분 문자열 S[a...], S[b...]의 길이 2. S[a] == S[b] 인 경우 dp(a, b) = 1 + dp(a+1, b+1) 3. S[a] != S[b]인 경우 dp(a, b) = 0 1. dp(a, b): 가장 길게 일치하는 부분 문자열 S[a...], S[b...]의 길이 2번 이상만 등장하면 되므로, 서로 다른 시작점 2개가 있으면 된다. 따라서 dp(a, b)를 위와 같이 정의하자. 2. S[a] == S[b] 인 경우 dp(a, b) = 1 + dp(a+1, b+1) S[a] == S[b]인 경우, 첫 글자가 일치하므로 1+ dp(a+1, b+1)이 된다. 3. S[a] != S[b]인 경우 dp(a, b) = 0 첫 글자부터 일치하지 않는..
2022. 5. 12.
