다이나믹 프로그래밍2 백준 9251번 : LCS[java] 1. 첫 번째 문자열(s1)과 두 번째 문자열(s2)를 입력받는다. 2. dp에 사용할 배열 dp[1001][1001]을 만든다. ㄴ dp[i][j]는 s1의 i번째와 s2의 j번째 문자까지 비교했을 때 최장 공통 부분수열이다. 3. s1의 i번째 문자와 s2의 j번째 문자를 비교하고 같다면 dp[i][j] = dp[i-1][j-1] +1 이고, → s1의 i번째 문자와 s2의 j번째 문자를 이번 dp[i][j]에서 공통 문자로 사용했기 때문에 직전까지의 최댓값에 +1을 한다. 4. s1의 i번째 문자와 s2의 j번째 문자를 비교하고 다르다면 dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) 이다. → i번째 문자와 j번째 문자가 다르기 때문에 직전 문자열에 각각 추가하여 비교한 최.. 2023. 2. 22. 백준 11066번 : 파일합치기[java] dp[i][j]는 i번 파일부터 j번 파일을 합치는데 든 최소비용이다. dp[i][i]는 chapter[i]이고, dp[i][i+1]은 chapter[i] + chapter[i+1] = sum[i] - sum[i-1]이다. dp[i][i+2]부턴 i과 i+1번을 합친 후 i+2번을 합치기, i+1번과 i+2번을 합친 후 i번을 합치기 중 선택해야 한다. 이를 식으로 나타내면, dp[i][i] + dp[i+1][i+2] + (sum[i+2] - sum[i-1]) 와 dp[i][i+1] + dp[i+2][i+2] + (sum[i+2] - sum[i-1]) 중 더 작은 수가 dp[i][i+2]이다. sum[i+2] - sum[i-1]은 현재 합치려는 파일 2개를 합치는데 사용하는데 드는 비용이다. 여기서 fr.. 2023. 2. 10. 이전 1 다음 반응형
