11066 파일 합치기[DP]

S/W 엔지니어를 포기할 까 고민하게 만든 문제였다.

결국 많이 풀어봐야 할 것 같다,, DP문제를 풀 때, 습관적? 고정관념적으로 

DP[n] = DP[n-1] + DP[n-2] 처럼 매우 1차원적으로 점진적으로 값이 (오른쪽으로) 쌓여간다는 생각을 하게된다.

이렇게 1차원 적으로 DP문제를 접근하면 절~~~ 대로 풀 수 없는 문제인 것 같다.

우선 이 문제를 풀기 위한 핵심은

1. 파일이 합쳐 지는 원리(계산)

2. DP 점화식 세우기

1번 같은 경우 문제를 "정확히" 분석하지 않고 냅다 코딩부터 하니... 2번을 올바르게 세웠더라도 이 문제는 시간초과로 틀렸을 것이다. 여기서 가장 중요한 사실은 인접한 경우에만 합칠 수 있다는 것!

1~2개는 굳이 점화식이 필요없이 계산이 가능하다. 하지만 3장 부터가 본격적인 문제.

A, B, C 가 있다면 최소를 구하기 위해서는

(A+B) + (A+B+C)  VS (B+C)+(A+B+C)    // (A+C)+(A+B+C)는 안된다!! A와 C가 인접하지 않았기 때문에!

(A+B+C를 즉, 단계마다 총 갯수의 합을 매번 더해야한다는 사실을 잘 인지해야 한다.)

2번에서 점화식을 세우기 위해서는

DP[i][j] 라는 형식을 사용하였다. i~j까지의 계산량을 뜻하는 것인데 처음에는 도저히 못풀겠어서 다른 분들의 코드를 봐도 이해가 가지 않았다.

DP에서는 문제를 정의해 이처럼 수식? 코드?로 표현하는게 매우 중요하더라..

아무튼. 1차원적인 사고에서 벗어나 DP[i][j]를 적용하면

DP[i][j] = DP[i][k] + DP[k+1][j] + i~j까지의 합.

이라고 정리 할 수 있다.

DP값은 해당 문제에서 최소를 구해야 하기에 주기적으로 min 값을 교채해줘야 한다.

(따라서 아래 코드에서 보는바와 같이 DP를 -1로 초기화 한 후, DP[s][e]에 매번 MAX를 넣어주고 비교 연산을 한다. 이렇게 하지 않는다면... -1이 무조건 들어가겠지? -1로 한 이유는 DFS 에서 백트래킹 하는 원리와 비슷하게 방문한 곳인지 체크하기 위함이다.)

코드:

#include <iostream>

#include <algorithm>

#define INF 0x7fffffff/2

using namespace std;

int DP[501][501];

int arr[501];

int sum[501];

int F(int s, int e){

if (s >= e) return 0;

if (DP[s][e] != -1) return DP[s][e];

if (e == s + 1) return arr[s] + arr[e];

DP[s][e] = INF;

for (int i = s; i <= e; i++){

int tmp = F(s, i) + F(i + 1, e) + sum[e] - sum[s - 1];

DP[s][e] = min(DP[s][e], tmp);

}

return DP[s][e];

}

int main(){

int TC;

cin >> TC;

while (TC--){

int N;

cin >> N;

for (int i = 1; i <= N; i++){

cin >> arr[i];

sum[i] = sum[i - 1] + arr[i];

}

for (int i = 1; i <= N; i++){

for (int j = 1; j <= N; j++){

DP[i][j] = -1;

}

}

cout << F(1, N) << endl;

}

system("pause");

return 0;

}