Cooper's devlog

쉬운 계단 수 : 10844번 - JAVA 본문

Algorithm/Baekjoon

쉬운 계단 수 : 10844번 - JAVA

cooper_dev 2020. 7. 17. 20:03

1. 문제 링크

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

 

10844번: 쉬운 계단 수

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

www.acmicpc.net

 

2. 문제 설명

3. 문제 접근

-규칙성을 파악하는 것이 핵심포인트!

-중요 조건 : 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

 

[1]배열 생성 : 끝자리 값을 의미하는 배열을 생성한다.

 

 

(1) n = 1

0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1
X (1) (2) (3) (4) (5) (6) (7) (8) (9)

 

 

 

 

 

 

(2) n = 2(※규칙성 파악)

0 1 2 3 4 5 6 7 8 9
1 2 2 2 2 2 2 2 2 1
(10) (10,21) (12,32) (23,43) (34,54) (45,65) (56,76) (67,87) (78,98) (89)

 

1.끝자리 == 0

0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1
X (1) (2) (3) (4) (5) (6) (7) (8) (9)
1 2 2 2 2 2 2 2 2 1
(10) (21) (12,32) (23,43) (34,54) (45,65) (56,76) (67,87) (78,98) (89)

 

식 : stair[row][col] = stair[row-1][col+1];

2. 1< 끝자리 < 9

0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1
X (1) (2) (3) (4) (5) (6) (7) (8) (9)
1 1 2 2 2 2 2 2 2 1
(10) (21) (12,32) (23,43) (34,54) (45,65) (56,76) (67,87) (78,98) (89)

 

식 : stair[row][col] = stair[row-1][col+1];stair[row][col] = stair[row-1][col-1] + stair[row-1][col+1];

3. 끝자리 == 9

0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1
X (1) (2) (3) (4) (5) (6) (7) (8) (9)
1 2 2 2 2 2 2 2 2 1
(11) (21) (12,32) (23,43) (34,54) (45,65) (56,76) (67,87) (78,98) (89)

 

식 : stair[row][col] = stair[row-1][col+1];stair[row][col] = stair[row-1][col-1];

 

4. 문제 풀이

 

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
package dp1;
import java.util.Scanner;
public class easy_bridge_num {
    static final int div = 1000000000;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.nextLine());
        long[][] stair = new long[n+1][10];
        
        for (int col = 1; col <= 9; col++)    stair[1][col] = 1;
        
        for (int row = 2; row <= n; row++) {
            for (int col = 0; col <= 9; col++) {
                if(col == 0)                            stair[row][col] = stair[row-1][col+1];
                else if(col == 9)                       stair[row][col] = stair[row-1][col-1];
                else                                    stair[row][col] = stair[row-1][col-1] + stair[row-1][col+1];
                
                stair[row][col] %= div;
            }
        }
        
        long ans = 0;
        for (int i = 0; i <= 9; i++)    ans += stair[n][i];
        System.out.println(ans % div);
        
        sc.close();
    }
}
  
 
 
  

4. 느낀점 혹은 개선 사항

1. 예외가 두 경우가 있어 규칙성을 찾는데 생각해야 하는 부분이 좀 있었다.

 

'Algorithm > Baekjoon' 카테고리의 다른 글

가장 큰 증가 부분 수열:11055번 - JAVA  (0) 2020.07.21
동물원: 1309번 - JAVA  (0) 2020.07.17
정수 삼각형: 1932번 - JAVA  (0) 2020.07.16
포도주 시식:2156번-JAVA  (0) 2020.07.16
스티커:9465번 - JAVA  (0) 2020.07.16
'Algorithm/Baekjoon' Related Articles more
Comments