[백준] #3040. 백설공주와 일곱난쟁이들 (Python)

✔ 문제 #10844. 쉬운 계단의 수

💡 인접한 모든 자리의 차이가 1인 계단수가 있다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구한다. 0으로 시작하지 않는다.

 

input : N (1≤N≤100)

output: 정답을 1,000,000,000로 나눈 나머지

input

1

2

output

9

17

✔ 풀이과정

💡 힌트 : 구구단 코드와 비슷하다, 테이블을 사용한다. 각각의 케이스를 구분하자.(if문)

 

모든 경우의 수를 구하는 것이다. 근데 하나하나 다 풀려고 하면 너무 복잡해진다.

각각의 케이스를 구해보자. N이 1일 때, 자리수가 1이기 때문에 각 숫자들이 맨 뒷자리에 올 수 있는 개수는 1씩이다.

• 맨 뒤에 0이 올 수 있는 경우의 수 - 0으로 시작할 수 없고, 1만 올 수 있다. ⇒ (1개)
• 맨 뒤에 1이 올 수 있는 경우의 수 - 21가 올 수 있다. 01은 올 수 없다. ⇒(1개)
• 맨 뒤에 2가 올 수 있는 경우의 수 - 12, 32가 올 수 있다. ⇒(2개)
• 맨 뒤에 9이 올 수 있는 경우의 수 - 8만 올 수 있다. ⇒(1개)

i \ j 0 1 2 3 4 5 6 7 8 9

1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2

따라서 이를 이용해서 테이블을 만들고 해당 점화식을 세운다!

i = 자리수(N), j = 맨 뒤에 갈 수 있는 경우의 수

j = 0 → num[i][j] = num[i-1][1]

j = 9 → num[i][j] = num[i-1][8]

j = 2~8 → num[i][j] = num[i-1][j-1] + num[i-1][j]

내 풀이

n = int(input())

num = [[0]*10 for _ in range(n+1)]
num[0] = [1,1,1,1,1,1,1,1,0] #0행에 들어가는 값들을 계단수의 경우의수로 초기화

for i in range(1,n+1):
    for j in range(10): #0일때, 9일때, 나머지인 경우를 점화식을 토대로 코드 작성
        if j == 0: 
            num[i][j] = num[i-1][1]
        elif j == 9:
            num[i][j] = num[i-1][8]
        else:
            num[i][j] = num[i-1][j-1] + num[i-1][j]

answer = sum(num[n]) % 100000000
print(answer)

이 풀이는 런타임에러가 난다.

다른 풀이

n = int(input())

num = [[0]*10 for _ in range(n+1)]
num[0] = [0,1,1,1,1,1,1,1,1]

for i in range(1,n+1):
    for j in range(10):
        if j == 0:
            num[i][j] = num[i-1][j+1]
        elif j == 9:
            num[i][j] = num[i-1][j-1]
        else:
            num[i][j] = num[i-1][j-1] + num[i-1][j+1]

answer = sum(num[n]) % 100000000
print(answer)

---

✔ 회고

동적계획법 (Dynamic Programming, DP)

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식
• ↔ 그리디알고리즘과 반대 (모든 해를 구하지 않고, 닥치는 순간만 구함)
• 그리디 알고리즘에 비해 시간은 오래 걸리지만, 결과적으로 항상 최적의 해를 구할 수 있음
• ex. 피보나치 수열

이 문제는 동적계획법에 대한 예제이다. 직접 다 풀지는 못했지만, 동적계획법이 어떤 것인지 알게 되었다.

여러 번 반복되는 경우, 테이블이나 배열을 이용하여 기억공간에 저장해두었다가 불러올 수 있다는 것을 알게 되었다.