https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. Logic 먼저 dp테이블의 의미는 dp[i] i개의 돌에서 턴을 잡은 사람의 승패 유무이다. 문제에서 1개, 3개, 4개를 가져갈 수 있다고 했고 항상 상근이가 먼저 시작한다고 했기 때문에 돌 갯수 | 우승자 1개 | 상근이 2개 | 창영이 3개 | 상근이 4개 | 상근이 항상 이렇게 이기고 이후는 이전에 메모이제이션 된 값으로 부분문제가 쪼개지기 때문에 DP로 풀 수 있다. 항상 두 사람이 완벽하게 게임을 한다고 했으며 항상 상근이가 먼저 시작하기 때문에 한번이라도 상근이가 이기는 경우가 생기면 해당 n개..
다이나믹 프로그래밍
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. Logic - 첫번째 문자부터 확인하면서 각 문자열의 끝까지 확인하고 만약 각 인덱스의 서로의 문자가 같으면 값 +1 Topdown형식으로 풀었다. 2. Code #include using namespace std; int dp[1001][1001]; string str1, str2; int solve(int s1Idx, int s2Idx) { /..
