글 읽기 - 2차원배열DP풀이 - "50%에서 틀렸습니다" 질문드립니다.

developer_p 1년 전 0

안녕하세요. 1차원배열로 푸는게 더 쉽고 대부분이 그렇게 푸신걸 알고는 있습니다.

근데 처음 생각했던 풀이가 2차원 배열로 푸는거라 풀어보고 싶은데, 50%에서 틀렸습니다. 가 뜹니다.

매우 흡사한 문제인 백준 2293번도 풀었는데...

비슷한 2차원배열 풀이를 참고해도 똑같습니다. (https://d-cron.tistory.com/23)

어느 부분이 잘못됐는지, 혹은 반례 등 도움을 주실 수 있으실까요?

감사합니다.

// MARK: - 9084번(DP - 반복문)
import Foundation
let T = Int(readLine()!)!
for _ in 0..<T {
    let N = Int(readLine()!)!
    let coins: [Int] = [0] + readLine()!.split(separator: " ").map{Int(String($0))!}
    let M = Int(readLine()!)!
    
    var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: M + 1), count: N + 1)
    
    for i in 0...N { // 각 행의 1열 모두 1로 초기화.
        dp[i][0] = 1
    }
    
    for i in 1...N {
        for j in stride(from: coins[i], through: M, by: 1) { // 동전의 가치가 구해야 하는 합M보다 클 때, 에러를 방지하기 위해.
            let temp = dp[i - 1][j] + dp[i][j - coins[i]]
            
            if temp > Int(pow(2.0, 31.0)) - 1 { // 경우의 수가 2^31 -1을 벗어나는 경우, 에러를 방지하기 위해.
                dp[i][j] = 0
            }
            else {
                dp[i][j] += temp
            }
        }
    }
    
    print(dp[N][M])
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2차원배열DP풀이 - "50%에서 틀렸습니다" 질문드립니다.

developer_p 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말