Algorithm/BOJ

[C++/ 백준 11066번] 파일 합치기 - DP(다이나믹 프로그래밍), prefixsum(누적합)

Rubi ❤️ 2025. 6. 7. 18:33
728x90
반응형

📚 [C++/ 백준 11066번] 파일 합치기 - DP(다이나믹 프로그래밍), prefixsum(누적합)

🔍 문제 요약

  • 문제링크 : 백준 11066번
  • 주요 태그: DP 다이나믹프로그래밍, prefixsum 누적합

 

소설을 여러 장으로 나누어 작성하며, 각 장은 서로 다른 파일로 저장된다. 이 파일들을 하나로 합치기 위해 두 개씩 계속 합치기를 반복한다.

이때 두 파일을 합치는 데 드는 비용은 두 파일의 크기의 합이다.

파일의 순서를 바꿀 수는 없으며, 모든 파일을 하나로 합치기 위한 최소 비용을 구해보자.

💡 문제 분석

  • 입력:
    • 테스트케이스 수 T
    • 각 테스트케이스마다 K (파일 개수), 그리고 각 파일의 크기 (정수 K개)
  • 출력:
    • 각 테스트케이스마다 모든 파일을 하나로 합치기 위한 최소 비용
  • 제한 조건:
    • 3 ≤ K ≤ 500
    • 파일 크기 ≤ 10,000
    • 파일 순서 변경 불가

🔑 아이디어

  • 순서가 고정된 채로 최소 비용을 구하기
    • 다이나믹 프로그래밍(DP) 방식 중 구간 DP(Interval DP) 를 사용
  • dp[i][j]: i번째부터 j번째 파일까지 하나로 합치는 최소 비용
  • 모든 가능한 분할점 k에 대해, 구간 [i~k], [k+1~j]를 각각 합친 비용 + 이 둘을 합치는 비용을 계산한다.

🧩 풀이 전략

✅ DP 테이블 정의

dp[i][j] = i부터 j까지의 파일을 하나로 합치기 위한 최소 비용

✅ 누적합(prefixSum) 정의

파일 합치는 데 필요한 비용은 해당 구간의 총합 
누적합을 이용해 구간합을 O(1)로 계산할 수 있다.

prefixSum[i] = board[1] + board[2] + ... + board[i]
sum(i~j) = prefixSum[j] - prefixSum[i-1]

✅ 점화식

for (int k = i; k < j; k++) {
    dp[i][j] = min(dp[i][j],
                   dp[i][k] + dp[k + 1][j] + sum(i~j));
}
  • [i, j]를 k를 기준으로 나누고
  • 왼쪽 파일 묶음 + 오른쪽 파일 묶음 + 두 묶음을 합치는 비용(전체 크기 합)

📦 예제 입력 & 출력

입력
2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

출력
300
864

🖥️ 코드 (C++)

#include <iostream>
#include <climits>

using namespace std;

int board[501];
int prefixSum[501];
int dp[501][501];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;

		fill(board , board + n + 1, 0);
		fill(prefixSum , prefixSum + n + 1, 0);
		for (int i = 0; i <= n; i++) {
			fill(dp[i] , dp[i] + n+1, 0);
		}

		for (int i = 1; i <= n; i++) {
			cin >> board[i];
			prefixSum[i] = prefixSum[i - 1] + board[i];
		}
		
        //누적합 중 가장 큰 것 고르기 - 길이 2인 것 부터 시작해 늘려서 찾기
		//첫 번째 합 + 첫 번째 합 + 두 번째 값 = 두 번째 값 +  두 번째 값합 + 현재 값 ..
        //구간 DP
		for (int len = 2; len <= n; len++) {
			for (int i = 1; i <= n - len + 1; i++) {
				int j = i + len - 1;
				dp[i][j] = INT_MAX;
				for(int k = i; k < j; k++) {
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]
					+ prefixSum[j] - prefixSum[i- 1]);
				}
			}
		}

		cout << dp[1][n] << "\n";
	}
	return 0;
}

✅ 검증 및 테스트

🔍 예제 1: [40, 30, 30, 50]

가능한 병합 방식 중,

  • (40+30) = 70, (30+50) = 80 → 최종 (70+80) = 150
  • 총 비용: 70 + 80 + 150 = 300

🔍 예제 2: [1, 21, 3, 4, 5, 35, 5, 4, 3, 5, 98, 21, 14, 17, 32]

구간이 많아 직접 계산은 어렵지만, DP 테이블에 의해 최적 병합 경로를 찾아
최소 비용 = 864로 출력됩니다.

⏱️ 시간 복잡도

  • 시간:
    삼중 루프 → O(N³) = 500³ = 1.25억 → 충분히 해결 가능
  • 공간:
    dp[501][501], prefixSum[501], board[501] → O(N²)

✨ 결론

항목 내용
문제 유형 구간 DP
사용 기법 prefixSum, 삼중 반복문, 최적 분할점 탐색
핵심 포인트 누적합을 활용한 구간 합 계산, 모든 분할점 시도
추천 학습자 중급 이상 DP 연습자, 최적화 알고리즘 연습자

 

이 문제는 구간 DP의 전형적인 구조와 누적합 기법을 모두 익힐 수 있었다.
특히 dp[i][j] = min(dp[i][k] + dp[k+1][j] + 합) 패턴은 자주 보이는 유형이라고 하니 숙지해두면 좋을 것 같다.

728x90
반응형