백준 10844번, '쉬운 계단 수' 풀이과정 및 코드 / C++, Python

백준 10844번 '쉬운 계단 수' 풀이과정 및 코드

---

문제 설명

수의 길이 N이 주어지면, 해당 길이의 수 중에서 인접한 모든 자리 수의 차이가 1이 나는 계단 수의 개수를 구하여 1,000,000,000으로 나눈 나머지를 반환한다. N은 1보다 크거나 같고 100보다 작거나 같다.

주의할 점

1. 계단 수는 '인접한 모든 자리수의 차이가 1 이하인 수'가 아니라, '인접한 모든 자리수의 차이가 1인 수'라는 점. 동일한 숫자나 2 이상 차이가 나는 숫자는 연달아서 올 수 없다.
2. 맨 마지막 숫자가 무엇이냐에 따라서 자리수가 하나 늘었을 때 올 수 있는 숫자의 개수가 달라진다는 점.
   -> 예를 들어 마지막 숫자가 9라면 그 뒤에는 무조건 8 밖에 올 수 없고, 마지막 숫자가 0이라면 그 뒤에는 무조건 1만 올 수 있다. 그 사이의 수들은 자신보다 하나 작거나 큰 수가 모두 뒤에 붙을 수 있다.
3. N이 수의 길이인데 최대범위가 100이기 때문에 자칫하면 자료형의 최대값을 넘을 위험이 있다는 점. 1,000,000,000으로 중간 중간에 나누어주어야 이를 방지할 수 있다.

생각의 흐름

1. 수의 길이에 따른 계단 수의 개수를 캐시에 저장해두어서 재귀함수나 for문으로 바로 구해야겠다!
2. 생각해보니까 계단 수를 정확히 구하려면 전체 계단 수에 0이나 9로 끝나는 숫자가 얼마나 되는지를 알아야 하네
3. 수의 길이에 따른 계단 수의 개수를 마지막 숫자가 뭐냐에 따라 나누어 저장해두고, 그로부터 다음 계단 수를 구해야겠다.

코드

C++

#include <stdio.h>

long dp[101][10];

int main(void){
  int n;
  long answer = 0;
  scanf("%d",&n);

  for(int i = 1; i<10; i++)
    dp[1][i] = 1; //한자리 수인 경우 초기화. 0은 첫 번째 자리에 올 수 없으므로 제외.

  for(int l = 1; l<=n; l++){
    for(int i = 0; i<10; i++){
      if(i!=9){ //9가 아니라면 i보다 하나 큰 숫자가 i 뒤에 붙을 수 있음
        dp[l+1][i+1] += (dp[l][i]%1000000000);
      }
      if(i!=0){ //0이 아니라면 i보다 하나 작은 숫자가 i 뒤에 붙을 수 있음
        dp[l+1][i-1] += (dp[l][i]%1000000000); 
      }
    }
  }

  for(int i = 0; i<10; i++){
    answer = (answer + dp[n][i])%1000000000;
  }

  printf("%ld",answer);

}

위의 코드처럼 작성한다면, dp에 값을 대입하는 부분에서 dp[l][i]를 먼저 나눈 후에 dp[l+1][i+1]와 더하기를 시행하기 때문에 dp를 int형으로 생성한다면 오버플로우가 발생한다. 이는 괄호가 없어도 마찬가지이다.

따라서 dp 배열을 int보다 큰 long이나 long long으로 지정하든지, dp[l+1][i+1] = (dp[l+1][i+1] + dp[l][i]) % 1000000000로 바꾸어야 한다.

이런 것을 신경쓰지 않아도 되는 python을 쓰는 것도 방법 중에 하나다.

Python

n = int(input())
dp = list(list(0 for _ in range(10)) for _ in range(n))

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

for i in range(n-1):
  for j in range(10):
    if(j!=0):
      dp[i+1][j-1] = dp[i+1][j-1] + dp[i][j] % 1000000000
    if(j!=9):
      dp[i+1][j+1] = dp[i+1][j+1] + dp[i][j] % 1000000000
print(sum(dp[n-1])%1000000000)

디버깅 기록

1. 조금이라도 연산이 복잡해지면 구현을 망설이는 습관이 나도 모르게 생겼다. 분명 더 쉽고 편한 길이 있을지도 모른다는 생각이 들어서 괜히 이것 저것 시도해보다가 오히려 더 돌아가게 된다. 요령 피울 생각하지말고 정직하게, 답이 나오는 방법이고 시간 초과가 나지 않을 것 같다면 구현을 해보자.

   
   

2. 데이터형의 최대범위를 반드시 반드시 명심하자!!! mod 연산을 한 후에 값을 출력한다면, 다른 연산(더하기, 곱하기 등)을 모두 시행한 후에 mod 연산을 하자. 결과값이 범위를 초과하지 않도록..