Post

코딩테스트: 쉬운 계단수 (백준 10844)

Posted
By ayaysir
14 min read

문제: 쉬운 계단수

45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

  • 입력: 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
  • 출력: 첫째 줄에 정답을 1,000,000,000(10억)으로 나눈 나머지를 출력한다.

 

예제 입출력
  • 1 => 9
  • 2 => 17

 

해답

Python 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

n = int(input())
divisor = 1000000000
dp = [[0] * 10 for _ in range(101)]

for i in range(1, 10):
    dp[1][i] = 1

for i in range(2, n + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i - 1][1] % divisor
        elif j == 9:
            dp[i][j] = dp[i - 1][8] % divisor
        else:
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % divisor

print(sum(dp[n]) % divisor)

 

Swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

let n = Int(readLine()!)!, divisor = 1000000000
var dp = Array(repeating: Array(repeating: 0, count: 10), count: 101)
for i in 1...9 {
    dp[1][i] = 1
}

for i in stride(from: 2, through: n, by: 1) {
    for j in stride(from: 0, through: 9, by: 1) {
        switch j {
        case 0:
            dp[i][j] = dp[i-1][1] % divisor
        case 9:
            dp[i][j] = dp[i-1][8] % divisor
        default:
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % divisor
        }
    }
}

print(dp[n].reduce(0, +) % divisor)
  • 동적 프로그래밍 (Dynamic Programming)을 사용합니다.
  • DP[자리수][맨_끝자리에_오는_수] 의 2차원 배열을 사용하며, 맨 끝자리에 오는 수에 따라 점화식을 다르게 지정합니다.
    • 0인 경우 dp[i][j] = dp[i-1][1]
    • 9인 경우 dp[i][j] = dp[i-1][8]
    • 그 외의 경우 dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])
    • 점화식 도출 과정은 풀이 섹션에 있습니다.
  • 중간 계산 과정에서 산술 오버플로(arithmetic overflow)를 방지하기 위해 나머지를 취하며 (x % divisor), 마지막 계산 과정에서 요구하는 답을 얻기 위해 한 번 더 나머지를 취합니다.
    • 이에 대한 자세한 설명은 참고 섹션에 있습니다.

 

풀이

먼저 계단수가 얼마나 만들어질 수 있는지 경우의 수를 따집니다.

  • 자릿수별로 살펴볼 때, 자리수 = 1인 경우 0을 제외한 나머지 숫자는 계단수입니다.
    • 문제에서 한자리에 대한 구체적인 언급은 없습니다. 한자리인 경우 인접한 다른 자릿수가 없습니다.
    • 그러나 예제 입출력에서 1 => 9가 있었기 때문에 이를 토대로 한 자리 숫자는 1부터 9까지 계단수라고 정의합니다.
    • 경우의 수는 9입니다.
  • 모든 계단수에서 0은 맨 앞에 위치할 수 없고, 1~9는 맨 앞에 위치할 수 있습니다.
  • 자리수 = 2 인 경우
    • 마지막 자리가 9일때, 앞에는 8만 올 수 있으므로 경우의 수는 1입니다. (89)
    • 마지막 자리가 0일때, 앞에는 1만 올 수 있으므로 경우의 수는 1입니다. (10)
    • 마지막 자리가 1일때, 앞에는 2만 올 수 있으므로 경우의 수는 1입니다. (21)
    • 마지막 자리가 (2~8)일때, 앞에는 (1~7)과 (3~9)가 올 수 있으므로 경우의 수는 2입니다.
      • 예를 들어 마지막 자리가 4인 경우 (34, 54)입니다.
  • 자리수 = 3인 경우
    • 마지막 자리가 9일때, 앞에는 8만 올 수 있고
      • 8 앞에는 7과 9가 올 수 있으므로
      • 가능한 경우는 (789, 989), 경우의 수는 2입니다.
    • 마지막 자리가 0일때, 앞에는 1만 올 수 있고
      • 1 앞에는 2만 올 수 있으므로
      • 가능한 경우는 (210), 경우의 수는 1입니다.
    • 마지막 자리가 1일때, 앞에는 2만 올 수 있고 (=> 맨 앞에는 0이 올 수 없습니다.)
      • 0 앞에는 1만 올 수 있고
      • 2 앞에는 1, 3이 올 수 있으므로
      • 가능한 경우는 (102, 121, 321), 경우의 수는 3입니다.
    • 마지막 자리가 2일때, 앞에는 1과 3이 올 수 있고
      • 1 앞에는 2만 올 수 있고
      • 3 앞에는 2, 4가 올 수 있으므로
      • 가능한 경우는 (212, 232, 432), 경우의 수는 3입니다.
    • 마지막 자리가 (3~8)일때, 앞에는 앞에는 (2~7)과 (4~9)가 올 수 있고,
      • 이 경우 각각 앞에는 두 개의 숫자가 올 수 있으므로
        • 예를 들어 4 앞에는 3과 5가 올 수 있습니다.
      •  경우의 수는 4가 됩니다.
        • 예를 들어 마지막 자리가 4인 경우 (234, 434, 454, 654) 가 가능한 경우입니다.

 

같은 자리수라도 마지막 자리에 따라 나올 수 있는 경우의 수가 달라지므로 1차원적으로 다룰 수는 없습니다. 테이블 표(2차원 배열)를 그려서 생각해봅니다.

  • 세로축은 자리수이며, 가로축은 맨 끝에 오는 숫자를 뜻합니다.
    • 테이블의 각 칸은 경우의 수입니다.
    • 세로축은 i, 가로축은 J로 놓고 2차원 배열을 사용합니다.
    • 예를 들어 DP[2][0]의 값은 하늘색 칸의 1이며, DP[2][1]은 분홍색 칸의 1입니다.
  • 자리수 0은 0으로 초기화합니다. (표의 - 부분)
    • 자리수가 0인 경우는 있을 수 없으므로 경우의 수는 0입니다.
    • 자리수가 0인 경우는 일반화된 점화식에서 필요합니다.
  • 자리수 1은 앞에서 언급했듯이 경우의 수는 1입니다.
    • 자리수가 1인데 맨 뒷자리가 0인 경우는 성립할 수 없으므로 0으로 둡니다.
    • 점화식을 따라 DP[1-1][1] = 0을 가져오는 것으로 생각할 수도 있습니다.
  • 자리수 2와 3도 똑같이 채웁니다.
  • 여기서 규칙을 발견할 수 있습니다. 규칙에 따라 도출된 점화식을 이용해 계산합니다.
    • 맨 끝 숫자가 0인 경우에는 앞에 1밖에 올 수 없으므로 이전 자리수의 경우의 수 중 맨 끝이 1인 자릿수를 가져옵니다.
      • DP[i][0] = DP[i - 1][1]
      • i=1, j=0인 경우에는 DP[0][1] = 0에서 가져옵니다.
    • 맨 끝 숫자가 9인 경우에는 앞에 8밖에 올 수 없으므로 이전 자리수의 경우의 수 중 맨 끝이 8인 자릿수를 가져옵니다.
      • DP[i][0] = DP[i - 1][8]
    • 나머지 경우는 앞에 두 숫자가 올 수 있으므로 이전 자릿수에서 j-1, j+1인 경우의 수를 가져와서 더해줍니다. (대각선 화살표 참조)
      • DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1]
      • 표의 경우 초록색, 노란색 칠한 곳이 해당 부분입니다.
      • 색칠하지 않은 영역도 마찬가지로 똑같은 규칙이 적용됩니다.
      • 앞에서 경우의 수를 도출하는 과정에서는 앞의 숫자가 2인 경우와 3~8인 경우를 다르게 취급했지만, 일반화된 점화식에서는 맨 끝 숫자가 2인 경우 앞 숫자가 1인 경우의 수와 3인 경우의 수를 더하고, 맨 끝 숫자가 3인 경우 앞 숫자가 (2, 4)인 경우의 수를 더하므로 동일한 식으로 계산할 수 있습니다.

 

참고: 나머지를 중간 계산과정에서도 해야하는 이유

결론부터 말하자면, 중간에 나머지를 안하면 산술 오버플로(arithmetic overflow)라는 유형의 런타임 에러가 발생하기 때문입니다.

나머지를 하지 않은 상태에서 문제에서 요구하는 최대값인 n = 100을 입력하면 다음과 같이 계산됩니다.

예) 중간 계산 과정에서 나머지를 하지 않은 경우 (=> 컴파일러 터짐)
  • dp[68][2] = 8,833,413,110,019,436,605
  • dp[67][1] = 3,292,956,562,874,470,358, dp[67][3] = 5,540,456,547,144,966,247
  • dp[68][3] = 산술 오버플로우 (Swift runtime failure: arithmetic overflow)
  •   => 9,770,621,288,303,265,298으로 Int(64비트)의 최대 범위인 9,223,372,036,854,775,807을 넘어선다.
  • dp[67][2] = 4,230,164,741,158,299,051, dp[67][4] = 5,540,456,547,144,966,247

읽을수도 없는 천문학적인 숫자가 나오면서 for문의 i = 68번째에서 산술 오버플로가 발생합니다. 중간 계산과정에서 나머지를 하면 산술 오버플로를 방지할 수 있습니다.

예) 중간 계산 과정에서 나머지를 한 경우
  • dp[68][2] = 19,436,605
  • dp[67][1] = 874,470,358, dp[67][3] = 144,966,247
  • dp[68][3] = 303,265,298 (=> 산술 오버플로 발생 안함)
  • dp[67][2] = 158,299,051, dp[67][4] = 144,966,247

동일한 배열 주소에서 값 차이가 확연하게 벌어진 것을 알 수 있습니다.

 

그러면 중간에 했는데 마지막에 나머지는 왜 또 하나요?

나머지 공식이 성립해야 하기 때문입니다. 나머지 연산자 성질 중에 다음과 같은 공식이 있습니다.

따라서 위 코드의 계산 결과는 최종 결과에도 나머지를 해야만 성립하게 됩니다.

예를 들어 n = 50인 경우 중간 나머지를 하지 않았을 때와, 중간 나머지를 했을 때 최종적인 답의 계산 과정은 다음과 같습니다.

중간 나머지를 했더라도 나머지 공식에 의해 최종합은 문제에서 원하는 답이 아니므로, 마지막 최종 결과에서도 나머지를 다시 해서 원하는 결과를 만들어야 합니다.

DevLog, 코딩테스트
This post is licensed under CC BY 4.0 by the author.