더 많이 실패하기

백준 10844번 쉬운 계단수 Java (☆공부 266일차) 본문

알고리즘/백준

백준 10844번 쉬운 계단수 Java (☆공부 266일차)

김발자~ 2023. 4. 22. 16:02
반응형

10844 쉬운 계단 수

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

 

10844번: 쉬운 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

 

 


백준 10844번 문제 쉬운 계단 수


문제


 

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 125386 39883 28847 30.068%

문제

45656이란 수를 보자.

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

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

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

17

 

 

 


과정 생각해보기 & 오답


 

https://gimbalja.tistory.com/247

 

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

10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 10844번 문제 쉬운 계단 수 문제 과정 생각해보기 &

gimbalja.tistory.com

4달 전에 푼 문제

 

2차원 배열을 이용한다 int[자수][오는숫자]
몇 개든 마지막 자리가 0이면 앞에는 1만 올 수 있고
마지막 자리가 9면 8만 올 수 있고
마지막 자리가 1~8이면 각각 0,2 / 2,4 / 3,5 / 4,6 / 5,7 / 6,8 / 7,9가 올 수 있다

 

따라서 점화식은 아래와 같다
i자리가 0이면 dp[i][0] = dp[i-1][1]
i자리가 9이면 dp[i][9] = dp[i-1][8]
i자리가 1~8이면 dp[i-1][j-1] + dp[i-1][j+1]

 

 

 


정답 인정 코드


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
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];    // 100자리까지
        final int MOD = 1_000_000_000;
        
        for(int i = 1; i < 10; i++) {
            dp[1][i] = 1;    // 1~9
        }
        
        for(int i = 2; i < n+1; i++) {    // n자리까지
            for(int j = 0; j < 10; j++) {    // 각 자릿수 0~9
                if(j == 0) {
                    dp[i][0= dp[i-1][1] % MOD;
                }else if(j == 9) {
                    dp[i][9= dp[i-1][8] % MOD;
                }else {
                    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);
    }
 
}
 
cs

 

 

 


 

 

반응형
Comments