백준 10844번 쉬운 계단 수

문제 링크

문제 전략

• d[N][j] : 길이가 N인 숫자이면서 마지막 숫자가 J일때 계단수의 갯수 라고 정의
• 그렇게 정의를 했을 때의 점화식을 세우고 N=0일때는 d[0] = 0이고 N=1일때 마지막 숫자가 0이 오지 못하므로 d[1][0]=0이고 나머지는 1로 초기화
• j가 9일때 0일때 예외가 발생하므로 예외처리
• 출력을 1000000000 나눈 나머지 이므로 (a+b)%C = (a%c + b%c) %C 성립하고 d배열에 저장되는 값을 1000000000보다는 작게 만들기 위해서 아래와 같이 코드를 작성
• d[1]은 앞에서 초기화를 다했으므로 i는 2부터 N까지 반복문을 돈다.
• 최종적으로 결과를 낼때에는 d[N][0]~d[N][9]까지의 합이므로 sum 함수로 한번에 더해준다.

알고리즘 종류

• 다이나믹 프로그래밍

N = int(input()) # 1<=N<=100
d = [[0]*10 if i != 1 else [1]*10 for i in range(N+1)]
# d[1] = 1로 초기화 , 나머지는 0으로 초기화
d[1][0] = 0
mod = 1000000000
for i in range(2,N+1):
  for j in range(10): # j: 0~9
    if j == 9:
      d[i][j] = d[i-1][j-1] 
    elif j ==0:
      d[i][j] = d[i-1][j+1]
    else:
      d[i][j] = d[i-1][j+1] + d[i-1][j-1]
    d[i][j] %= mod

result = sum(d[N]) % mod
print(result)

---

모범답안

d = [[0]*10 for _ in range(100+1)]
mod = 1000000000 
n = int(input())
for i in range(1, 10):
    d[1][i] = 1
for i in range(2, n+1):
    for j in range(10):
        d[i][j] = 0
        if j-1 >= 0:
            d[i][j] += d[i-1][j-1]
        if j+1 <= 9:
            d[i][j] += d[i-1][j+1]
        d[i][j] %= mod
ans = sum(d[n]) % mod
print(ans)