공부 126일차: 백준 10844번 쉬운 계단 수 자바 java

10844 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

 

 

 

---

백준 10844번 문제 쉬운 계단 수

---

문제

---

 

 

 

---

과정 생각해보기 & 오답

---

 

위의 그림처럼, 1부터 9까지 그려보면서 3, 4자리의 수를 구해본 결과

자리수	1	2	3	4
개수	9	17	35	69

이렇게 나오길래 짝수면 이전수 개수 * 2 - 1, 홀수면 이전수 개수 * 2 + 1인 규칙인 줄 알았는데 아니었다

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        int[] dp = new int[101]; // 1 ~ 100
        dp[1] = 9;
        
        for(int i = 2; i < n+1; i++) {
            if(i % 2 == 0) {    // 짝수라면
                dp[i] = (dp[i-1]*2)-1;
            }else {    // 홀수라면
                dp[i] = (dp[i-1]*2)+1;
            }
        }
        
        System.out.println(dp[n]);
        
    }
 
}
 

애초에 숫자를 잘못 구해서 생긴 문제였다

 

그래서 다시 차근차근 구해보았고, 2차원 배열로 풀면 되겠다는 생각이 들었다

(계속해서 위의 그림처럼 -1, +1 두 개씩 나눠서 구했다)

 

0은 1만, 9는 8만 될 수 있으니 제외하고, (n-1)의 -1, +1일 때의 숫자를 더하면 되는 것이다

 

 

---

정답 인정 코드

---

 

import java.io.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        int[][] dp = new int[101][10];
        int mod = 1_000_000_000;
        
        for(int i = 1; i < 10; i++) {
            dp[1][i] = 1;    //1자리수에는 각각의 수가 들어가는 경우만 가능
        }
        
        for(int i = 2; i < n+1; i++) {
            for(int j = 0; j < 10; j++) {
                if(j == 0) {
                    // i번째 수가 0이라면 i-1번째에는 1만 올 수 있다
                    dp[i][0] = dp[i-1][1] % mod;
                }else if(j == 9) {
                    // i번째 수가 9라면 i-1번째에는 8만 올 수 있다
                    dp[i][9] = dp[i-1][8] % mod;
                }else {
                    // i번째 수가 1~8이라면 i-1번째에는 [0,2]~[7,9]가 올 수 있다
                    dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1]) % mod;
                }
            }
        }
        
        int answer = 0;
        for(int i = 0; i < 10; i++) {
            // 오버플로우를 막기 위한 % 연산
            answer += dp[n][i] % mod;
            answer %= mod;
        }
        
        System.out.println(answer);
        
    }
 
}
 

 

https://code-lab1.tistory.com/108

이 블로그에서 확실히 정리할 수 있었다

 

 

---