[백준 5557] 1학년 (Swift)

https://www.acmicpc.net/problem/5557

 

DP (+DFS?)

 

숫자들의 배열을 보고, 그 숫자들 사이를 덧셈뺄셈으로 채워서 맨 마지막 숫자를 만드는 등식의 개수를 출력하는 문제

 

접근방법

처음에 봤을 때는 DFS로 풀면 되겠다 했는데, 경우의 수를 세는 문제라 DP를 사용해야하는 문제였다.

DP 규칙으로는 i번째까지 계산했을 때 나올 수 있는 숫자 : 경우의 수 를 갖는 딕셔너리를 원소로 갖는 배열을 만들었다.

DFS로 풀 생각을 했는데 이렇게 배열로 가능한 경우를 저장해두는 식이라 for문으로만 가도 풀 수 있었다.

for문으로 가지만, 딕셔너리 key가 dfs에서의 다음 노드를 의미하기 때문에 DFS 방식인건 변함없다.

 

이렇게 해서 마지막에서 두번째 원소의 딕셔너리 중에서 마지막 숫자랑 같은 key 값의 value를 출력하면 된다.

 

오답노트

경우의수 DP 문제 풀 때는 늘! 이전 노드에서 경우의수를 그대로 더해줘야 한다는걸 까먹으면 안된다!

(이번에도 까먹어서 2 나오길래 dp 출력해보고 깨달음..)

 

소스코드

import Foundation

func solution() -> Int {
    
    // input
    let n: Int = Int(readLine()!)!
    let num: [Int] = readLine()?.split(separator: " ").map { Int($0)! } as! [Int]
    
    // data
    var result: Int = 0
    var dp: [[Int:Int]] = [[Int:Int]](repeating: [:], count: n) // i번째 연산자까지 계산했을 때 나올 수 있는 값:경우의 수 들의 집합
    
    // process
    dp[0][num[0]] = 1
    
    for i in 1..<n-1 {
        for pre in dp[i-1] {
            // 더할 때
            let newAdd = pre.key + num[i]
            if newAdd >= 0 && newAdd <= 20 {
                dp[i][newAdd, default: 0] += pre.value
            }
            // 뺄 때
            let newRed = pre.key - num[i]
            if newRed >= 0 && newRed <= 20 {
                dp[i][newRed, default: 0] += pre.value
            }
        }
    }
    
    result = dp[n-2][num[n-1], default: 0]
    
    // output
    return result
}

print(solution())