[Algorithm/BOJ] 5557 - 1학년 (DP) Swift

문제풀이:

완전탐색으로 접근하면 시간초과가 난다. 그러면 DP로 풀어야 하는데 DP는 항상 접근 방법을 찾기가 어려웠다.

이전의 숫자 정보와 덧셈과 뺄셈을 진행할 index를 필요로 해서 2차원 배열로 사용해야 한다.

위 그림과 같이 처음에 dp[0][8]을 시작으로 다음 수인 3을 뺀 결과와 더한 결과가 0보다 크거나 같고 20보다 작거나 같으면 dp에 값을 저장한다. 이후는 같은 과정으로 진행하고 마지막 수에 해당하는 경우의 수를 출력한다.

 

코드: 

let n = Int(readLine()!)!
var nums = readLine()!.split(separator: " ").map { Int(String($0))! }
var dp = [[Int]](repeating: [Int](repeating: 0, count: 21), count: n)

dp[0][nums[0]] = 1

for i in 1 ..< n-1 {
    for j in 0 ..< 21 {
        if dp[i-1][j] != 0 {
            let plusNext = j + nums[i]
            let minusNext = j - nums[i]
            
            if 0 <= plusNext, plusNext <= 20 {
                dp[i][plusNext] += dp[i-1][j]
            }
            if 0 <= minusNext, minusNext <= 20 {
                dp[i][minusNext] += dp[i-1][j]
            }
        }
    }
}
print(dp[n-2][nums[n-1]])

 

문제:

5557번: 1학년