2024 - 12 - 30 오늘의 문제

 

문제 링크

백준 11066번 파일 합치기

https://www.acmicpc.net/problem/11066

 

---

 

문제 설명

 

 

---

문제 풀이

힌트 여부 : O

 

해당 문제는 DP 문제이니 점화식을 세워보자

1시간 동안 고민해도 도저히 답이 나오질 않는다 사실 더하고 그 뒤에 2번째 값과 비교하여 더한 값이 더 크면 바로 뒤에 값과 더한 값을 더하고 아니면 뒤에 2개의 값을 더하는 식으로 생각을 했으나 직접 다 더 해본 결과 답이 이상하게 나왔다

덕분에 구글에서 힌트를 봤는데

 

dp[i][j] 는 i 부터 j 페이지까지 페이지를 합한 최솟값

dp[i][i] 는 i페이지부터 i페이지까지 즉 i페이지의 값인 arr[i] 값이 된다

dp[i][i+1] 은 i페이지부터 i + 1 페이지까지 arr[i] + arr[i+1] 값이 된다

dp[i][i+2]는  전체를 더한 값 + dp[i][i] + dp[i+1][i+2]  vs  전체를 더한 값 + dp[i][i+1] + dp[i+2][i+2] 중 작은 값이다.

 

for (int i = 1; i <= k; i++) {
    for (int j = 1; j + i <= k; j++) {
        int t = j + i;
        dp[j][t] = Integer.MAX_VALUE;
        for (int d = j; d < t; d++) {
            dp[j][t] = Math.min(dp[j][t], dp[j][d] + dp[d + 1][t] + sum[t] - sum[j - 1]);
        }
    }
}

 

 

사실 코드를 완벽하게 이해하진 못했으나 핵심 코드는 3중 포문이다.

i 값이 몇장을 묶을 것인가

j 값이 어디부터 묶을 것인가

d 값이 특정 지점으로 나누기

역할을 한다고 하는데 나중에 다시 풀어보면서 이해해야할 것 같다!

 

참고 링크

https://guy-who-writes-sourcecode.tistory.com/43