[BOJ] 10844 쉬운 계단 수 - JAVA

1. 문제

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

10844번: 쉬운 계단 수

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

---

2. 풀이

규칙

최선을 다해 그려봤다.ㅋㅋㅋ

• N=1일때, 0빼고 1~9까지 한번씩 모두 가능하다. 그래서 N=1일때 계단수는 9다.
• N=2일때, 각 숫자는 자신의 양 옆에 있는 숫자값을 더해서 구할 수 있다.
• 예를 들면, N=1인 숫자 중 5는 N=2가 됐을 때 다음 수로 4와 6 중에 선택할 수 있다.
  • 5 --> 54, 56 가능, 76 --> 765, 767 가능
• 반대의 경우로 예를 들면, N=2인 숫자 중 마지막이 5인 숫자는 N=1일때 4,6인 숫자의 다음에만 존재할 수 있다. 
  • 4,6 --> n5 --> 45,65
• 각 단계의 요소는 그 전 단계의 요소-1, 요소+1에서만 만들어질 수 있다.
• 따라서 식을 이렇게 세울 수 있다.
• dp[N][i] = dp[N-1][i-1]+dp[N-1][i+1]

 

코드

• i는 계단수의 길이, j는 각 요소들이다. 
• 요소의 숫자가 0보다 클 때만 nums[i-1][j-1]을 더한다. 요소의 숫자가 9보다 작을때만 nums[i-1][j+1]에 더한다. 양쪽의 끝 값이기 때문이다.
• N길이의 계단수를 다 구했다면 각 요소를 더해야한다. 이때 주의해야할 점은 %DIV의 위치다.
  • (A+B)%DIV = (A%DIV+B%DIV)%DIV 식을 잘 기억하자! 꼭 더해준 뒤에도 나머지연산을 해야한다.

import java.io.*;

public class BOJ_10844_쉬운계단수 {
   public static void main(String[] args) throws IOException {
      int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
      int DIV = 1000000000;

      int[][] nums = new int[N][10];
      nums[0] = new int[]{0, 1, 1, 1, 1, 1, 1, 1, 1, 1};

      for (int i = 1; i < N; i++) {
         for (int j = 0; j < 10; j++) {
            nums[i][j] += ((j > 0 ? nums[i - 1][j - 1] : 0) + (j < 9 ? nums[i - 1][j + 1] : 0)) % DIV;
         }
      }

      int sum = 0;
      for (int i = 0; i < 10; i++) {
         sum = (sum + nums[N - 1][i]) % DIV; 
      }

      System.out.println(sum);
   }
}

---

3. 결과

말도 안되는 규칙을 찾아서(피보나치인줄알았다..) 2번 틀렸고 한 번은 Arrays.stream(nums[N-1]).sum()써서, 또 한번은 += 연산 써서 틀렸다. 

1) Arrays.stream(nums[N-1]).sum() 쓰면 안되는 이유 -> 더하면서 %DIV연산이 안되기 때문이다. %를 하지 않으면 계속 더하는 과정에서 오버플로우가 생긴다.

2) sum += nums[N-1][i]%DIV 하면 안되는 이유 -> 무엇보다 중요한 건 (A+B)%DIV = (A%DIV+B%DIV)%DIV란 점이다. 각각 %DIV한 값을 더한 뒤 마지막으로 또 %DIV를 해야하는데, 이 코드는 각각 %DIV한 값을 더할 뿐 더한 뒤 %DIV하는 연산이 없다.

이 코드의 실행은 (nums[N-1][i]%DIV)에 sum을 더하고 그 값을 sum에 저장하는 순서로 가는데, 이미 nums[]배열은 위에서 %연산을 마친 뒤다. sum을 더하는 과정에서 %가 필요한 건 (sum+nums[N-1][i])%DIV이지 각각 %한 값을 다시 %할 필요가 없다. 아무 의미 없는 연산이라는 소리다.