백준 10844번 문제(쉬운 계단 수) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

10844번: 쉬운 계단 수

 

정답 코드는 아래와 같습니다.

import sys
 
def solve():
  n = int(sys.stdin.readline().rstrip())
  arr = [[0] * 10 for _ in range(n)]
  for i in range(1, 10):
    arr[0][i] = 1
  for i in range(1, n):
    arr[i][0] = arr[i-1][1]
    arr[i][9] = arr[i-1][8]
    for j in range(1, 9):
      arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1]
  rst = 0
  for i in range(10):
    rst += arr[n-1][i]
  print(rst % 1000000000)
 
solve()

 

저는 지문을 읽고 계단 수가 무엇인지 정확히 이해되지 않았습니다.(특히 한 자리 수인 경우)

이런 일은 실전 코딩테스트에서 생각보다 자주 발생합니다.

지문을 여러 번 읽어서 정확하게 이해하는 것도 좋은 방법이지만,

주어진 예제 입력과 출력이 어떻게 구해지는지 직접 나열해나가면서 이해하는 것도 좋습니다.

이럴 경우, 어떤 식으로 답을 구하면 좋을지도 같이 떠올릴 수 있기 때문에 제가 자주 사용하는 방식입니다.

 

728x90

 

이 문제의 예제 입력은 1과 2인데, 직접 해보면 자연스럽게 3에 대해서는 어떻게 되는지 해볼 수 있게 됩니다.

그리고 자릿수가 하나씩 증가할 때마다 맨 뒤에 숫자에 따라 뒤에 올 수 있는 경우가 결정되어 있다는 것을 알 수 있습니다. 즉, 0이나 9의 경우 그 뒤에 올 수 있는 숫자가 반드시 1이나, 8밖에 없고, 나머지 숫자들은 모두 뒤에 하나 증가한 수와 하나 감소한 수가 올 수 있다는 것입니다.

따라서 맨 뒤에 숫자가 각각 몇 개 있는지 histogram 을 만들고, 이 histogram 을 1인 경우부터 n 인 경우까지 update 하고, 마지막 n 번째 table에 적혀 있는 값들의 합이 결국 계단 수의 총 갯수가 될 것입니다.

(글로 쓰니까 좀 설명이 복잡한데, 동영상으로 보시면 그렇게 복잡하진 않습니다)

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=Rn9G6VrBKb4 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)