[Java] 백준 10844번 : 쉬운 계단 수 <Silver 1>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

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

10844번: 쉬운 계단 수

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    void run() throws IOException {
        long arr[][] = new long[101][11];
        int N = Integer.parseInt(bf.readLine());
        long sum = 0;

        for(int i = 1; i < 10; i++){
            arr[1][i] = 1;
        }

        for(int i = 2; i < N+1; i++){
            arr[i][0] = arr[i-1][1];
            for(int j = 1; j < 10; j++){
                arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1])%1000000000;
            }
        }

        for(int i = 0; i < 10; i++){
            sum += arr[N][i];
        }

        System.out.println(sum % 1000000000);
    }

    public static void main(String[] args) {
        Main my = new Main();
        try{
            my.run();
        }catch(Exception e){}
    }
}

---

Code 필수 요소

1. Dynamic Programming(동적 프로그래밍) 사용

2. 규칙 찾기

 

// Dynamic Programming(동적 프로그래밍) 사용

한동안 계속해서 풀 예정인 Dynamic Programming문제의 핵심은 이 문제가 Dynamic Programming을 사용해야 한다는 것을 깨닫는 것이다. 

 

// 규칙 찾기

이거 찾기가 진짜 힘들었다.

한자리 숫자가

1

2

3

4

5

6

7

8

9

 

두자리 숫자가

10

12

21

23

32

34

43

45

54

56

65

67

76

78

87

89

98

 

이걸보다보면 맨 뒷자리 숫자에서 +1, -1 한 값이 추가 된다. 그렇기 때문에 각 자릿수별로 맨 뒤에 무슨 숫자가 몇개 왔는지를 구한다면, 다음 자릿수때 해당 숫자로 끝나는 쉬운 계단 수의 갯수를 구할 수 있다.

0의 경우는 -1의 수가 없고, 9의 경우는 +1의 수가 없기 때문에 따로 규칙을 적용시켰다.

 

그런데 long타입으로 배열을 만들 경우 자동으로 0으로 초기화 되기 때문에 9는 특별한 규칙을 적용시키지 않고, 0이 포함되어있는 배열을 통해 -1의 경우 + 0 의 방식으로 작성했다.

 

// 전체적 설명

바텀업 방식을 사용하여 ArryList에 해당하는 값을 하나씩 저장하며 해당 값에 접근한다.

 

동적 계획법이란? 

https://naemamdaelo.tistory.com/27

알고리즘 - Dynamic Programming(동적 계획법)

 

코드를 간단하게 만든다고 배열을 한칸 더 추가했는데 이러면 만들어지는 칸 수가 확 늘어나게 된다. 과연 코드 깔끔한게 나을까 메모리 더 먹는게 나을까? 이건 모르겠다. 걍 for문 1칸 줄이고 마지막에 쓰는게 나을거 같은데 라는 생각이 들어 아래처럼 코드를 고쳐봤다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    void run() throws IOException {
        long arr[][] = new long[101][10];
        int N = Integer.parseInt(bf.readLine());
        long sum = 0;

        for(int i = 1; i < 10; i++){
            arr[1][i] = 1;
        }

        for(int i = 2; i < N+1; i++){
            arr[i][0] = arr[i-1][1];
            for(int j = 1; j < 9; j++){
                arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1])%1000000000;
            }
            arr[i][9] = arr[i-1][8];
        }

        for(int i = 0; i < 10; i++){
            sum += arr[N][i];
        }

        System.out.println(sum % 1000000000);
    }

    public static void main(String[] args) {
        Main my = new Main();
        try{
            my.run();
        }catch(Exception e){}
    }
}

이렇게 바꿨더니

위에 결과가 밑에 코드

이렇게 됐다.

음... 배열 칸 수가 줄었는데도 메모리는 오히려 더 쓰네. 속도는 왜 또 빨라졌는지 모르겠다.

아~~어려워~

 

 

-꿑-