• TOC {:toc}

이 글은 백준 온라인 저지의 11066번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2023.02.26

메모리 시간 코드 길이
22148 KB 1148 ms 1149 B 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [T, ...lines] = input;

function main(K, size) {
    const sum = Array.from(Array(K), () => Array(K).fill(0));
    const sizeSum = [...size];
    for (let i = 0; i < K - 1; i += 1) {
        sum[i][i + 1] = size[i] + size[i + 1];
        sizeSum[i + 1] = sizeSum[i] + size[i + 1];
    }

    for (let k = 2; k < K; k += 1) {
        for (let i = 0; i < K - k; i += 1) {
            const cardssize = sizeSum[i + k] - sizeSum[i] + size[i];
            for (let l = 0; l < k; l += 1) {
                if (!sum[i][i + k]) {
                    sum[i][i + k] = sum[i][i + l] + sum[i + l + 1][i + k] + cardssize;
                } else {
                    sum[i][i + k] = Math.min(sum[i][i + k], sum[i][i + l] + sum[i + l + 1][i + k] + cardssize);
                }
            }
        }
    }

    return sum[0][K - 1];
}

const res = [];
for (let t = 0; t < T; t += 1) {
    const K = parseInt(lines[2 * t]);
    const size = lines[2 * t + 1].split(" ").map((n) => parseInt(n));
    res.push(main(K, size));
}
console.log(res.join("\n"));

아이디어 & 풀이

DP를 이용하는 문제로 합치는 페이지 수(k)를 키워가면서 i 페이지부터 j 페이지까지 합치는데 드는 비용(sum)을 계산한다.

우선 dp 배열인 sum을 초기화 한다.

  • K x K의 2차원 배열을 만들고 0으로 초기화 한다.
  • sum[i][i]의 경우 해당 페이지(i)를 합치는 비용은 필요하지 않다.
  • sum[i][i + 1]의 경우 단순히 인접한 두 페이지의 비용을 더하면 된다.

주어진 첫 번째 예제의 경우 초기화 하면 다음과 같다.

j/i 0 1 2 3
0 0 70 0 0
1 . 0 60 0
2 . . 0 80
3 . . . 0

이 이후부터는 페이지 차이(k)를 늘려가면서 각 페이지들을 합치는데 드는 비용을 계산한다.

  • 즉 위의 표에서 대각선을 한 칸씩 위로 올리면서 값을 채운다고 생각할 수 있다.
  • 예를 들어 위의 예제에서는 k = 2인 경우는 (0, 2)와 (1, 3)이다.

우선 sum[0][2]부터 구해보자. sum[0][2]는 0, 1, 2 페이지를 합치는데 드는 비용으로 다음과 같이 두 묶음으로 나눌 수 있다.

  • 0 + (1 + 2)
    • 0 페이지는 단독 페이지이므로 만드는데 드는 비용이 없다 (sum[0][0]은 0).
    • (1 + 2) 페이지는 1 페이지에서 2 페이지를 우선 합쳐야하므로(sum[1][2]) 60이 필요하다.
    • 0 페이지와 (1 + 2)페이지를 합치는데는 0 페이지의 크기와(size[0]) (1 + 2) 페이지의 크기(size[1] + size[2])의 합만큼 비용이 필요하다.
  • (0 + 1) + 2
    • (0 + 1) 페이지는 0 페이지에서 1 페이지를 우선 합쳐야하므로(sum[0][1]) 70이 필요하다.
    • 2 페이지는 단독 페이지이므로 만드는데 드는 비용이 없다. (sum[2][2]은 0)
    • (0 + 1)페이지와 2 페이지를 합치는데는 (0 + 1) 페이지의 크기(size[0] + size[1])와 2 페이지의 크기(size[2])의 합만큼 비용이 필요하다.
  • 합치는 페이지의 묶음을 어떻게 나누더라도 최종적으로 두 묶음을 합치는 데 드는 비용은 묶이는 모든 페이지의 크기를 더한 값과 같은 것을 알 수 있다.

즉, 0, 1, 2 페이지를 합치는 데 드는 비용은 해당 페이지를 임의의 두 묶음으로 나눴을 때, 각 페이지를 만드는데 필요한 비용의 합에 의해 결정되고 그 값이 최소가 되도록 묶으면 된다.

  • 위의 경우는 60이 최솟값이고, 마지막에 페이지를 합치는 데는 40 + 30 + 30으로 100이라는 비용이 들기 때문에 sum[0][2]의 값은 160이다.

일반적으로 정리하면 sum[i][j]를 구하기 위해서는

  • 중간 지점 l를 정해서 i ~ j를 임의의 두 그룹으로 나눈다: (i ~ i + l) && (i + l + 1 ~ j)
  • 두 묶음을 만들기 위해 드는 비용을 구한다 sum[i][i + l] + sum[i + l + 1][j]
  • l의 값은 0부터 j - i까지 1씩 증가시키면서 위의 값중 최솟값을 구한다.
  • 구한 최솟값에 i ~ j의 크기의 합을 더한다.

대각 방향으로 이동하면서, 해당 대각선의 값을 순차적으로 구해서 끝까지 채운뒤 (0, K)의 값을 출력한다.

피드백

  • 마지막에 i ~ j까지의 크기의 합을 더할 때 입력받은 크기 배열을 slice(i, j + 1)해서 합을 계산하는 것 보다 미리 i번째 까지의 크기의 합의 배열(sizeSum)을 구한 다음 sizeSum[i]와 sizeSum[j + 1]의 차를 구하는 게 효율적이다.

참고 답안

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [T, ...lines] = input;

function main(K, size) {
    const sum = Array.from({ length: K }, () => [0]);
    const sizeSum = [0];
    const getsizeSum = (from, to) => sizeSum[to + 1] - sizeSum[from];

    for (let i = 0; i < K; i++) {
        sizeSum.push(sizeSum[sizeSum.length - 1] + size[i]);
        for (let j = 0; j < i; j++) {
            let min = sum[i - 1][j];
            for (let k = 0; k < j; k++) {
                min = Math.min(min, sum[i - j + k - 1][k] + sum[i][j - k]);
            }
            sum[i].push(min + getsizeSum(i - j - 1, i));
            }
        }
    return sum[K - 1][K - 1];
}

const res = [];
for (let t = 0; t < 2 * T; t += 2) {
    const K = parseInt(lines[t]);
    const size = lines[t + 1].split(" ").map((n) => parseInt(n));
    res.push(main(K, size));
}
console.log(res.join("\n"));

아이디어 & 풀이

위의 풀이에서는 K x K의 이차원 배열을 선언해 사용해서 좌측 아래 부분이 낭비됐는데 이를 방지할 수 있다.

  • 위의 풀이에서 이차원 배열을 선언하는 게 시간이 많이 드는지 위의 풀이에 비해 거의 두 배 가까이 빠르다 (실행시간 500ms 내외)

기본 원리는 위의 풀이와 동일하지만 배열을 다음과 같은 순서로 채우게 된다.

  • 위의 예제와 다르게 .이 찍혀있는 부분이 생성 자체가 안된다.
j/i 0 1 2 3
0 0 . . .
1 0 . . .
2 0 . . .
3 0 . . .
j/i 0 1 2 3
0 0 . . .
1 0 70 . .
2 0 . . .
3 0 . . .
j/i 0 1 2 3
0 0 . . .
1 0 70 . .
2 0 60 160 .
3 0 80 170 300