[알고리즘 PS] 백준 10844 쉬운 계단 수 자바 문제 풀이

문제

해당 포스팅은 백준의 10844번 쉬운 계단 수 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

우선 이 문제를 해결하기 위해서는 자리수에 대한 개념을 먼저 알아야 한다.

 

45765 이라는 수가 있다면 해당 수는 가장 왼쪽의 수가 제일 높은 자리 수가 된다.

즉

  4     5     7     6    5
5자리  4자리  3자리  2자리  1자리

그럼 우리는 이 문제를 n번쨰 자리와 n-1 번째 자리로 점화식을 만들 수 있다.

 

현재 n번째 자리에서 쓰일 수 있는 n-1 번쨰 자리의 숫자들의 쓰임 횟수를 더하면 최종 점화식이 나오게 된다.

a[n] = [n-1]

접근법

위의 점화식을 구성하기 위해 어떤 수가 n번째 자리에서 나올 수 있는지 알아보자.

 

n번쨰 자리의 수가 예를 들어 3이라고 하면 n-1번째 자리에서 사용될 수 있는 횟수는 총 2회이다.

23, 32.

그럼 모든 n번쨰 자리의 수 (0~9까지)는 위와 같이 2번 쓰일까?

 

다음 경우를 봐보자.

 

1. 0으로 시작하는 수는 없으나 0으로 끝나는 계단 수는 존재함. 즉 10 에서만 쓰일 수 있음
2. 9는 n-1번째 수의 8에서만 쓰일 수 있음.

거기에 우리가 찾은 조건 n번째 자리 수 m은 n-1번째에서 2번씩 사용됨을 추가하면 다음과 같은 점화식이 도출된다.

// n: n번쨰 자리수
// m: n자리 수에 해당하는 수 0 ~ 9

// m이 0인 경우
a[n][m] = a[n-1][1];
// m이 1 ~ 8 사이인 경우
a[n][m] = a[n-1][m+1] + a[n-1][m-1];

// m이 9인 경우
a[n][m] = a[n-1][9];

오답 후보

그리고 주의해야할 것이 이번에도 역시 mod 연산이 아닐까 싶다.

 

이번에는 기존 모듈러와 조금 다를 수 있다.

 

10억으로 나눈 나머지를 출력하라라는 이유가 우리가 어떤 수를 넘어가면 결과로 10억이 넘게 나와서 정수 오버플로가 발생하기 때문이다.

그럼 하나의 원소 값은 (arr[n][m]) 최대 10억이 될 수 있고 (arr[n])의 크기는 최대 100억 - arr[n][0]이 될 수 있다.

그래서 값을 저장할 때에도 모듈러를 수행해야 한다.

여기서 끝일까?

값을 저장할 때도 모듈러로 넣어줬으면 최악의 경우 출력할 때도 100억 언저리가 될 수 있으므로 출력을 할 때도 모듈러를 수행해주자.

이것 때문에 많이 틀렸다..

정답 코드

import java.io.*;
public class Main{
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());

    int[][] arr = new int[101][10];
    for(int i = 1; i <= 9; i++) arr[1][i] = 1;

    for(int i = 2; i <= n; i++){
      arr[i][0] = arr[i-1][1];
      arr[i][9] = arr[i-1][8];
      for(int j = 1; j <= 8; j++) {
        arr[i][j] = (arr[i-1][j+1] + arr[i-1][j-1]) % 1000000000;
      }
    }
    int answer = 0;

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

    bw.write(String.valueOf(answer));
    bw.flush();
    bw.close();
  }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.