[java 백준] 실버 1/ 10844번 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

bottom-up 방식으로 풀어보았다.

처음에 규칙을 잘못세워서 다른 사람들이 쓴 코드를 참고했다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static int n;
    public static long[][] dp;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
        dp = new long[n + 2][10];
        dp[1][0] = 0;
        for (int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j + 1] % 1000000000;
                } else if (j == 9) {
                    dp[i][j] = dp[i - 1][j - 1] % 1000000000;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] % 1000000000;
 
                }
 
            }
        }
        long count = 0;
        for (int i = 0; i < 10; i++) {
            count += (dp[n][i]) % 1000000000;
        }
        System.out.println(count % 1000000000);
 
    }
 
}

풀면서 잘못 생각한 부분

---

 

 

처음에 생각한 방식은 위 사진처럼 dp[i][j]=dp[i-1][j]+dp[i-2][j]의 점화식을 세우는 것이였다.

 

 

하지만 문제점은 1열애 있었다.

 

그 이유는 중간에 0도 들어갈 수 있다는 것을 생각하지 못했다. 

 즉, 세로를 기준으로 점화식을 세울 것이 아니라 가로를 기준으로  규칙을 세웠어야 했던 것이다. 

그럼 가로를 기준으로 규칙을 세우는 것이 무엇일까?

어차피 1차이 나는 수들의 경우를 구하는 것이기 때문에 열을 기준으로 점화식을 세우는 것이 맞다.

dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]이 된다.

 

하지만 0열과 9열은 예외인데

 

0열의 경우,

dp[i][0]=dp[i-1][1]

9열의 경우,

dp[i][9]=dp[i-1][8]이다. 

 

왜냐하면 0열이나 9열의 경우 전자는 왼쪽방향에서 오는 경우가 없고(0보다 작은 수는 없음), 후자는 오른쪽에서 오는 경우의 수(9보다 큰 수는 없음)가 없기 때문에 단방향의 점화식만 갖는다. 

 

결국 이친수 문제처럼 이번에도 합해지는 규칙을 잘못 짚어서 점화식도 잘못 세우게 된것이였다.

 

반례를 알고 싶을 때

---

https://www.acmicpc.net/board/view/60530

글 읽기 - 왜 틀린지 모르겠습니다

100을 넣어보면된다!