[백준(BOJ)] 2688 줄어들지 않아 - 스위프트 (Swift)

[Silver I] 줄어들지 않아 - 2688

문제 링크

성능 요약

메모리: 69100 KB, 시간: 12 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 2월 1일 11:44:39

문제 설명

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다.

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

출력

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

 

풀이

해당 문제를 풀기 위해선 DP를 이용하였습니다. dp[i][j]를 이용하여 i자리 숫자에서 가장 왼쪽에 j가 왔을 때 올 수 있는 숫자의 개수를 구하고자 하였습니다.

 

문제를 풀기 위해 i=2를 구해보았습니다.

dp[2][0]은 결국 한 자리 수의 모든 경우이기 때문에, dp[1][0] + dp[1][1] + ... + dp[1][9]와 같습니다.

dp[2][1]은 dp[1][0]을 제외한 한 자리 수의 모든 경우이기 때문에, dp[1][1] + dp[1][2] + ... dp[1][9]와 같습니다.

이러한 방식으로 대입하게 되면 dp[i][?]의 모든 값이 i자리 수의 숫자의 개수가 됩니다.

 

이를 코드로 구현하면 다음과 같습니다.

let t = Int(readLine()!)!

for _ in 0..<t {
    let n = Int(readLine()!)!

    var dp = [[Int]](repeating: [Int](repeating: 0, count: 10), count: 65)
    var ans = 0

    // 1자리
    for i in 0...9 {
        dp[1][i] = 1
    }

    if n >= 2 {
        // 2자리 이상
        for i in 2...n {
            for j in 0...9 {
                for k in j...9 {
                    dp[i][j] += dp[i-1][k]
                }
            }
        }
    }

    print(dp[n].reduce(0, +))
}