BOJ_11066_파일합치기

파일 합치기 문제를 이번엔 풀어 볼 예정입니다.

Bottom up 방식으로 풀어보려고 노력했으나 실력이 부족한 탓에..ㅠㅠ 

Top Down 방식으로 풀어보겠습니다.    문제는 다음과 같습니다.

파일을 겹쳐서 하나의 파일로 만들고 거기서 소비되는 비용을 계산하여 최소 값일 경우로 체크하는 문제

입니다. 

이를 해결하기 위해서 점화식을 세우면 D[i][j]라고 할 경우,

i 번째에서의 파일부터 j 번째 파일까지의 비용 계산 시 반환 되는 최소값이라고 할 수 있습니다.

점화식을 구체화시키기 위해서 아래와 같이 표현할 수 있습니다.

이렇게 k라는 변수를 두어서 i번째 파일부터 k번째 파일까지의 합 중 나오는 필요한 최소 비용 한 그룹과

K+1번째 파일부터 j번째 파일까지의 합 중 나오는 필요 최소 비용의 다른 한 그룹과의 합으로 

i번째 파일부터 j번째 파일까지의 합 중 최소 비용을 구할 수 있습니다.

추가로 각 위치마다의 파일의 비용을 같이 더해줘야 하기 때문에 아래와 같이 공식이 나오게 됩니다.

Top Down 방식으로 풀어보면 현재 i와 j 값으로 함수를 만들어 보면 다음과 같습니다.

---

private static int go(int[] a, int[][] d, int i, int j) {

if (i == j)

return 0;

if (d[i][j] > 0)

return d[i][j];

d[i][j] = 0;

int sum = 0;

for (int k = i; k <= j; k++) {

sum += a[k];

}

int ans = -1;

for (int k = i; k <= j - 1; k++) {

int temp = go(a,d,i,k) + go(a,d,k+1,j) + sum;

if (temp < ans || ans == -1) {

ans = temp;

}

}

d[i][j] = ans;

return d[i][j];

}

---

Top-Down 방식은 종료조건 그리고 memorization 조건이 중요합니다.

우선 종료 조건은 시작점인 i와 종료점이 j가 같을 경우, 0이 반환됩니다. (이동할 필요가 없기 때문)

그리고 memorization의 조건으로는 보통 0보다 클 경우 또는 경우의 수를 계산하는 d 배열을 모두 -1로 

초기화 한 다음에 -1이 아닐 경우 반환하도록 구현됩니다.

저는 0보다 클 경우로 구현하여 위와 같이 코드를 정리하였습니다.

이 후에는 i부터 j까지의 파일 각각의 합을 체크하는 반복문을 적어줍니다. 

다음은 go라는 함수가 i와 j를 가지고 구현하기 때문에 k만을 가지고 반복문 범위를 체크해주면 됩니다.

k 범위는 앞서 설정한대로 i부터 j-1까지이며 내부에 점화식대로 코드를 적어주면 됩니다.

단, 최소 비용을 계산한다는 점을 반드시 고려하여 조건을 정리해야 합니다.

전체 코드는 다음과 같습니다.

값을 추가하는 범위가 0부터 시작하면 0부터 체크하고 1부터 시작하면 1부터 체크하면 됩니다.

---

import java.util.Scanner;

public class 파일합치기2 {

private static Scanner scanner;

private static int t; // test case

private static int[][] d;

private static int[] a;

private static int n;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int t = scanner.nextInt(); // test case

while (t-- > 0) {

n = scanner.nextInt(); // 갯수

a = new int[n + 1];

d = new int[n + 1][n + 1];

for (int i = 1; i <= n; i++)

a[i] = scanner.nextInt();

System.out.println(go(a, d, 1, n));

}

}

private static int go(int[] a, int[][] d, int i, int j) {

if (i == j)

return 0;

if (d[i][j] > 0)

return d[i][j];

//d[i][j] = 0;

int sum = 0;

for (int k = i; k <= j; k++) {

sum += a[k];

}

int ans = -1;

for (int k = i; k <= j - 1; k++) {

int temp = go(a,d,i,k) + go(a,d,k+1,j) + sum;

if (temp < ans || ans == -1) {

ans = temp;

}

}

d[i][j] = ans;

return d[i][j];

}

}

---

감사합니다.