파일 합치기

개인적으로는 좀 어려웠던 문제인데

우선순위 큐?

문제를 읽어보면

... 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. ...

연속되도록 합쳐야 했는데, 나는 순서는 상관없이 합쳐도 된다고 생각했다. 그래서 문제를 끄적거리다보면, 그냥 우선순위 큐 쓰면 바로 해결되겠는데? 싶었다. 그런데 예제 테스트케이스대로 답이 나오지 않아서 살짝 멘붕했다가, 질문게시판에서 나랑 비슷한 실수를 한 사람들 덕분에 문제를 파악하게 되었다. 문제는 똑바로 읽어야 한다...

DP

어쨌든 이 문제의 카테고리는 DP였다. 나는 지금 SW 역량 테스트 준비 - 연습 문제집을 풀고 있기 때문에, 문제를 어떻게 접근해야 하는지 큰 힌트를 얻어 알 수 있다.

아무튼, 어떻게 해결해야할지 고민하다가 cost(a, b): a부터 b까지 파일을 합쳤을 때 최소비용의 형태로 문제를 정의할 수 있게 되었고, 이대로 구현에 들어갔다.

연속되게 합쳐야 하니까, 범위를 두 그룹으로 나누고 두 그룹으로 나누는 기준점인 m을 b쪽으로 이동시키면서(a <= m < b) 최소비용을 찾아나가는 식으로 단순하게 구현을 했다.

// ...
for m := a; m < b; m++ {
	*ret = min(*ret, cost(a, m) + cost(m+1, b))
}

문제는 이렇게 구현하면, 말 그대로 두 구간을 합치는 최소비용만 구해지는 것이고, 이는 단순히 a ~ b까지 더하는 결과만 나왔다는 것이었다.

합쳐지는 중간과정의 비용까지 계산을 해야한다. 결국 생각하다가 최종적으로 합쳐지는 비용은 a ~ b까지 한 번 또 더해야 된다는 것을 깨달았고, 부분합을 이용해서 최종적으로 문제를 해결했다.

답

package main

import (
    "bufio"
    "math"
    "os"
    "strconv"
)

var (
    sc *bufio.Scanner
    wr *bufio.Writer
)

func init() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)

    wr = bufio.NewWriter(os.Stdout)
}

func scanInt() int {
    sc.Scan()
    ret, _ := strconv.Atoi(sc.Text())
    return ret
}

var (
    files []int
    psum  []int
    dp    [][]int
)

func main() {
    tc := scanInt()
    for tci := 0; tci < tc; tci++ {
        l := scanInt()

        dp = make([][]int, l)
        for dpi := range dp {
            tmp := make([]int, l)
            tmp[0] = math.MaxInt64

            for ti := 1; ti < l; ti *= 2 {
                copy(tmp[ti:], tmp[:ti])
            }

            dp[dpi] = tmp
        }

        files = make([]int, l)
        psum = make([]int, l)
        files[0] = scanInt()
        psum[0] = files[0]
        for fi := 1; fi < l; fi++ {
            files[fi] = scanInt()
            psum[fi] = psum[fi-1] + files[fi]
        }

        wr.WriteString(strconv.Itoa(cost(0, l-1)))
        wr.WriteByte('\n')
    }

    wr.Flush()
}

func cost(a, b int) int {
    ret := &dp[a][b]
    if *ret != math.MaxInt64 {
        return *ret
    }

    if a == b {
        *ret = 0
        return 0
    }

    if b-a == 1 {
        *ret = files[a] + files[b]
        return *ret
    }

    sum := 0
    if a == 0 {
        sum = psum[b]
    } else {
        sum = psum[b] - psum[a-1]
    }

    for m := a; m < b; m++ {
        *ret = min(*ret, cost(a, m) + cost(m+1, b) + sum)
    }

    return *ret
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

문제는 이 코드가 1초가 걸렸다는 것인데, 상향식으로도 한 번 풀어보고 다른 분들의 풀이도 참고해서 다시 풀어봐야겠다.