[알고리즘] Swift -백준 #10844(쉬운 계단 수) -DP

문제링크

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

 

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17

 

 

 

 

분석

인접한 모든 자리의 차이가 1인 수 = 계단 수

길이가 n인 계단 수가 총 몇 개 인지 구하는 문제

0으로 시작할 수는 없다.

 

풀이 과정

0으로 시작하는 것 빼고 모든 자리에는 0부터 9까지 올 수 있다.

n= 2 를 보면 1 -> 12, 10 2 -> 21, 23 3 -> 32, 34 4 -> 43, 45 5 -> 54, 56 6 -> 65, 67 7 -> 76, 78 8 -> 87, 89 9 -> 98

n= 3 를 보면 1 -> 121, 123, 101 2 -> 210, 212, 232, 234 3 -> 321, 323, 343, 345 4 -> 432, 434, 454, 456 5 -> 543, 545, 565, 567 6 -> 654, 656, 676, 678 7 -> 765, 767, 787, 789 8 -> 876, 878, 898 9 -> 987, 989

마지막 숫자를 보면 앞의 숫자의 +1 이거나 -1 인 수이다.

 

n은 1보다 크거나 같고 100보다 작거나 같은 자연수

배열의 사이즈를 n의 크기에 맞게 설정해준다.

var map = Array(repeating: Array(repeating: 0, count: 10), count: 101)

for i in 0...9 {
    map[1][i] = 1
}

1의 자리수는 모두 1개이니까 1로 초기값을 설정해준다.

 

초기값을 설정해줄때 n=1일때는 9개를 더해주면 되고

2부터는 뒷자리를 더해줘야한다.

2자리수부터 반복을 해주고 마지막에 올 수 있는 수는 0~9이다.

조건문으로 0과 9일때는 따로 설정해준다.

0일 때는 1만 가능하고 9일때는 8만 가능하기 때문이다.

if n > 1 {
    for i in 2...n {
        for j in 0...9 {
            if j == 0 {
                map[i][j] = map[i-1][j+1] % 1000000000
            } else if j == 9 {
                map[i][j] = map[i-1][j-1] % 1000000000
            } else {
                map[i][j] = (map[i-1][j-1] + map[i-1][j+1]) % 1000000000
            }
        }
    }
}

저번 문제와 마찬가지로 오버플로우로 런타임에러가 나기떄문에 미리 나누기를 해주고 배열에 넣어준다.

 

마지막으로 해당하는 자리수의 합계를 더해준다.

var sum = 0
for i in 1...9 {
    sum = (sum + map[n][i]) % 1000000000
}

print(sum)

 

 

풀이

let n = Int(readLine()!)!

var map = Array(repeating: Array(repeating: 0, count: 10), count: 101)
for i in 0...9 {
    map[1][i] = 1
}

if n > 1 {
    for i in 2...n {
        for j in 0...9 {
            if j == 0 {
                map[i][j] = map[i-1][j+1] % 1000000000
            } else if j == 9 {
                map[i][j] = map[i-1][j-1] % 1000000000
            } else {
                map[i][j] = (map[i-1][j-1] + map[i-1][j+1]) % 1000000000
            }
        }
    }
}

var sum = 0
for i in 1...9 {
    sum = (sum + map[n][i]) % 1000000000
}

print(sum)

 

결과

 

 

 

---

📂  정리

DP의 문제는 점화식을 구하는 것이 가장 핵심이다.

문제의 규칙을 찾아서 풀어야한다.

규칙을 찾고 조건을 잘 구분하여 코드를 짜주면 된다..

지금 규칙을 찾는 거 까지는 가능하지만 조건이나 예외를 찾아서 구분해주는 것이 조금 어렵다..

다른 문제를 좀 더 풀어봐야 할 거 같다..

화이팅..