ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [java] 백준 알고리즘 10844번 쉬운 계단 수 풀이
    알고리즘/백준 알고리즘 2018. 5. 19. 10:34



    이 문제는 이중배열을 사용해야 풀 수 있었다


    이 문제를 푸는 가장 쉬운 방법은 이 문제는 이중배열을 사용해야 한다는 것과 4자릿수 정도까지 직접 써보면 된다.


    4자릿수를 다 완성하기 전에 이미 규칙을 깨닫게 된다.


    맨 앞자리가 1일 경우, 2번째 전 행의 앞자리 1인 계단 수 개수와 1번째 전 행의 앞자리가 2인 계단 수 개수를 합치면 된다.


    맨 앞자리가 2~8은, 1행 전의 해당 열의 -1,+1열을 더한 값과 같다


    맨 앞자리가 9는, 1행 전의 8열 계단 수와 같다.


    ** 한번 봅시다


    맨 앞 자릿수

     1

    2

     3

    4

    수의 길이: 1

     1

    (1)

    1

    (2) 

    1

    (3) 

     1

    (4)

    1

    (5) 

    1

    (6) 

    1

    (7) 

    1

    (8) 

    1

    (9) 

    수의 길이: 2 

     2

    (10,12)

    2

    (21,23) 

    2

    (32,34) 

    2

    (43,45) 

    2

    (54,56) 

    2

    (65,67) 

    2

    (76,78) 

    2

    (87,89) 

    1

    (98) 

    수의 길이: 3

     3

    (101,121,123)

    4

    (210,212,

    232,234) 

    4

    (321,323,

    343,345) 

    4

    (432,434,

    454,456) 

     4

    (543,545,

    565,567)

     4

    (654,656,

    676,678)

     4

    (765,767,

    787,789)

     3

    (876,878,

    898)

    2

    (987,989) 


    표에서 보듯이,


    수의 길이가 늘어날수록, 직전 수의 길이 계단 수에 영향을 받는다


    * 풀이소스


    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
    41
    42
    43
    44
    45
    46
    47
    public class Baekjoon10844{
     
        public static void main(String[] args) throws NumberFormatException, IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            
            int n = Integer.parseInt(br.readLine());
            long[][] stairArray = new long[100][9]; // 최대 100행까지 생길 수 있음
            long result = 0;
            
            for(int i=0; i<9; i++) {
                stairArray[0][i] = 1// 1행일 경우, 1~9까지 계단 수는 각각 1개다.
                
                /* 2자리수 배열 */
                if(i==8) { // 9에 해당하는 계단수(0부터 시작하기 때문에 8이다)
                    stairArray[1][i] = 1
                }else {
                    stairArray[1][i] = 2// 9를 제외하고 2자리 수 계단 수는 2개씩있다.
                }
            }
            
            if(n>2) {
                for(int i=2; i<n; i++) { // 3행부터 즉, 3자리수부터 시작하는 이유는 맨 앞 1이 나올 경우, 2번째 전 행의 값을 활용하기 위해서
                    
                    for(int j=0; j<9; j++) {
                        
                        if(j==0) {
                            stairArray[i][j] = (stairArray[i-2][j] + stairArray[i-1][j+1])%1000000000// 앞자리 1의 경우, 2번째 전의 행 앞자리 1값 + 1개 행 전의 앞자리 2의 값
                        }else if(j==8) {
                            stairArray[i][j] = (stairArray[i-1][j-1])%1000000000// 앞자리가 9의 경우, 1행 전의 앞자리가 8인 계단수들이다
                        }else {
                            stairArray[i][j] = (stairArray[i-1][j-1+ stairArray[i-1][j+1])%1000000000;
                        }
                    }
                }
            }
            
            for(int i=0; i<9; i++) {
                result += stairArray[n-1][i]; // 앞자리가 1~9인 계단수를 총 합치면 자릿수의 총 계단수가 나온다
            }
            bw.write(String.valueOf(result%1000000000));
            bw.flush();
            
        }
     
    }
     
    cs


Designed by Tistory.