[백준] 10844번 문제풀이

문제분석

• N 자릿수 계단 개수를 구하는 문제이다.
• 적용예제 분석
  - N=1 인 계단수는 1 2 3 4 5 6 7 8 9 으로 9개이다.
  - N=2 인 계단수는 10 21 32 43 54 65 76 87 98 89 78 67 56 45 34 23 12 으로 17가 있다.
  - 시작숫자가 1~8인경우, 두번째 숫자는 시작숫자-1, 시작숫자+1
  - 시작숫자가 9인 경우, 두번째 숫자는 8
  - N인 계단수를 구하기 위해 (N-1)인 계단수를 활용한다.
  - 길이가 2이고 시작숫자가 2인 계단수를 구하기 위해선 길이가 1이고, 시작숫자가 2인 수(1 또는 3)이 추가되어 21, 23을 만들 수 있다.
  -
• 다이나믹 프로그래밍 적용
  - 2차원 배열 dp, dp[i][j]는 길이 i, 마지막 숫자 j 인 계단수의 개수
  - 길이가 1인 계단수 1개 이므로 1로 초기화
  - dp[1][j] = 1 for j 1 to 9
  - j가 0일 때(0로 끝날때) 바로 앞 숫자는 1 만 가능
  - dp[i][0] = dp[i-1][1]
  - j가 9일 때(9로 끝날때) 바로 앞 숫자는 8 만 가능
  - dp[i][9] = dp[i-1][8]
  - 그 외의 경우(1부터~8까지)
  - dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

코드구현

n = int(input())  # 계단 수의 길이 입력 받기

# DP 테이블 초기화
dp = [[0] * 10 for _ in range(n + 1)]

# 길이가 1인 경우 초기값 설정
for i in range(1, 10):
    dp[1][i] = 1

# DP 테이블 갱신
for i in range(2, n + 1):
    for j in range(10):
        # 0과 9는 특별한 경우로 처리
        if j == 0:
            dp[i][j] = dp[i - 1][1]
        elif j == 9:
            dp[i][j] = dp[i - 1][8]
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

print(dp)
# 결과 계산
result = sum(dp[n]) % 1000000000
print(result)

결론

• 문제에서 말하는 N과 계단수의 의미가 너무 헷갈렸다. 이해하기 위해 여러 블로그를 참고했다.
• 쉬운 계단수? 쉽지 않다. 계단수 숫자 조합으로 접근하면 풀이가 어려워진다. 단순히 뒤에 나올 숫자 경우의 수만 저장하면 수월하다.
• 문제 5개를 풀면서 느낀 점은 DP는 동일한 연산의 결과가 반복 사용될 때 효율적이다.