[백준] 10844번 쉬운 계단 수 [Swift]

문제 링크

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자릿수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

문제 풀이

문제를 어떻게 접근할까... 하다가 하나의 규칙을 발견했습니다.

 

우선 간단하게 N = 1, N = 2, N = 3 일 때의 예시를 보겠습니다.

위의 그림을 보시게 되면 낮은 자리 수의 계단수는 큰 자리 수의 계단 수를 만드는데 중요한 역할을 합니다.

예를 들어 위의 그림에서 파란색으로 표현된 54라는 두 자리 계단수는 543, 545라는 세 자리 계단수를 만드는 역할을 하는 것입니다.

문제에서 조건으로 0으로 시작하는 수는 없다고 했기 때문에 하나를 더 생각해줘야 합니다.

1의 자리 수가 0이나 9인 경우에는 다음 자릿수를 만들 때 1개밖에 못 만든다는 점이죠!

그 외의 수들은 다음 자리수를 만들 때 2개씩 만들 수 있습니다.

 

이를 활용하면 N일 때 각 자리수를 알면 N+1의 계단 수의 개수를 구할 수 있게 됩니다.

 

즉 다이나믹 프로그래밍을 사용해서 각 자릿수마다 1의 자리에 있는 값들의 개수만 기억하면 N의 값에 따라 계단수의 개수를 구할 수 있게 됩니다!

 

유의할 점은 1의 자리 수가 0,9 일 때는 하나만 만들 수 있다는 점입니다.

 

이 문제는 N = 10이라면 10까지의 모든 계단 수를 구하라는 게 아니고 10에서의 계단 수의 개수만 알면 되기 때문에 저는 배열을 두 개 만들어서 번갈아가며 다이나믹 프로그래밍을 사용하는 방법을 택했습니다.

소스 코드

func solution() -> Int {
    let n = Int(String(readLine()!))!
    let mod = 1000000000
    if n == 1{
        return 9
    } else {
        var result: Int = 0
        var num1: [Int] = [Int](repeating: 1, count: 10)
        var num2: [Int] = [Int](repeating: 0, count: 10)
        num1[0] = 0
        
        for i in 1..<n{
            for j in 0..<num1.count {
                if i % 2 == 1 {
                    if j == 0 {
                        num2[0] = (num1[1]) % mod
                    } else if j == 9 {
                        num2[9] = (num1[8]) % mod
                    } else {
                        num2[j] = (num1[j+1] + num1[j-1]) % mod
                    }
                } else {
                    if j == 0 {
                        num1[0] = (num2[1]) % mod
                    } else if j == 9 {
                        num1[9] = (num2[8]) % mod
                    } else {
                        num1[j] = (num2[j+1] + num2[j-1]) % mod
                    }
                }
            }
        }

        if n % 2 == 1 {
            for i in num1 {
                result += i
            }
        } else {
            for i in num2 {
                result += i
            }
        }
        
        return result % mod
    }
}
print(solution())