[BOJ/5557/Golang] 백준 5557 - 1학년

문제로 바로 가기 : BOJ 5557 - 1학년

접근 방식

백준님의 강의 중 '연습'에 해당하는 DP 마지막 문제입니다. 1학년 문제는 LCS 문제 다음으로 나와서, LCS 풀듯이 푸는 건가 싶었는데, 일단 그건 아니었습니다.

두 번째로 생각했던 건, 일반적인 DP 문제를 풀 때 생각할 수 있는 마지막 수와의 관계를 생각해보았는데요, 여기에서 D[i][j] = i번째 수를 j가 0이면 더하여 현재 sum을 만드는 등식의 수, j가 1이면 빼서 현재 sum을 만드는 등식의 수라고 생각했습니다. 그러나 이 방법도 정답에 도달하지 못했습니다.

1시간 정도 고민 후에 어쩔 수 없이 참고 자료를 확인했는데요, 앞선 방법을 고민하다가 얼핏 생각했던 방식이 실제 문제를 푸는 점화식인 걸 확인하고,,, 눈물이 앞을 가리는 걸 느낄 수 있었습니다.

점화식은 매우 간단합니다. D[i][j] = D[i-1][j-A[i]] + D[i-1][j+A[i]]

D[i][j] 의 정의는 i 번째 수까지 활용해서 합 또는 뺄셈의 결과를 j로 만드는 등식의 수 입니다. 여기서 A[i]는 i 번째 숫자를 의미합니다.

즉, 현재 i 번째의 수까지 빼든 더하든 암튼 간에 활용해서 결과를 j로 만든다고 하면,

1. 직전의 환경인 i-1 번째 수까지를 활용해 만든 결과물은 j에서 A[i]를 뺀(즉, 추후 A[i]까지 더해서 최종으로 j를 만드는 등식) j-A[i] 이거나
2. j에서 A[i]를 더한(즉, 추후 A[i]까지 빼서 최종으로 j를 만드는 등식) j+A[i]일 것입니다.

따라서 D[i][j]는 D[i-1][j-A[i]]와 D[i-1][j+A[i]]라는 두 개의 작은 문제로 쪼개어 풀 수 있습니다.

이 때, 주의해야 할 점은, i == 1 일 때 입니다. i == 1 이라면, 현재의 j 즉, sum이 A[1]과 일치하는 지를 확인해야 합니다. 일치한다면, 1 을 넣고 리턴합니다. 더 하위로 내려갈 문제가 없을 뿐더러, 최소한 등식 한 개는 올바른 형태라는 것을 알 수 있기 때문입니다.

만약 두 값이 다르다면, 0을 리턴하면 됩니다.

점화식

// D[i][j] = i 번째 수까지 활용해서 합 또는 뺄셈의 결과를 j로 만드는 등식의 수
D[i][j] = D[i-1][j-A[i]] + D[i-1][j+A[i]]

코드

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

var (
    D      [][]int
    A      []int
    N      int
    answer int
)

func main() {
    defer w.Flush()
    N = scanInt()
    A = scanInts()
    D = make([][]int, N+1)
    for i := range D {
        D[i] = make([]int, 21)
        for j := range D[i] {
            D[i][j] = -1
        }
    }
    fmt.Fprintln(w, solve(N-1, A[N]))
}

func solve(idx, sum int) int {
    if idx <= 0 || 0 > sum || sum > 20 {
        return 0
    }
    if idx == 1 && sum == A[idx] {
        D[idx][sum] = 1
        return D[idx][sum]
    }
    if D[idx][sum] != -1 {
        return D[idx][sum]
    }
    D[idx][sum] = solve(idx-1, sum-A[idx]) + solve(idx-1, sum+A[idx])
    return D[idx][sum]
}

func scanInts() []int {
    sc.Scan()
    s := "0 " + sc.Text()
    t := strings.Fields(s)
    res := make([]int, len(t))
    for i := range t {
        res[i], _ = strconv.Atoi(t[i])
    }
    return res
}

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

마무리

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊