[백준] 11057번: 오르막 수 - Java, 자바

문제접근

이 문제는 이 전 쉬운 계단수와 비슷한 문제이다. 다른점이 있다면 이 문제에서는 0으로 시작할 수 있다는 것이다.
쉬운계단 수

이 문제는 손으로 직접 적어보면 쉽게 이해가 가능하다.
이 문제에서는 0으로 시작하는 숫자 또한 수로 인정하고 있다.
1자리를 예를 들면 0 ~ 9 까지 총 10가지가 가능 할 것이다.

다음으로 2자리를 예시로 들면, 2자리는 2번째 자리 즉 10의 자리가 0 일때 첫 번째 자리 1의 자리는 0 ~ 9 까지 가능하다. [인접한 수가 같아도 오름차순으로 쳐주기 때문에]
10의 자리 | 1의자리
0 | 0 ~ 9

이어서 2번 째 자리가 1일 때는 첫 번쨰 자리는 1 ~ 9 까지,
10의 자리 | 1의자리
1 | 1 ~ 9

2번 째 자리가 2일때는 첫 번째 자리는 2 ~9 까지....
2번 째 자리가 8일 때는 첫 번째 자리는 8 ~9 까지
2번 째 자리가 9일 때는 첫 번째 자리는 9 까지 가능하다.
10의 자리 | 1의자리
9 | 9 ~ 9

위의 규칙을 보자면 2번 째 자리의 값이 T 라면 첫 번째 자리의 값은 T ~ 9 까지 인것을 확인할 수 있다.
즉, 입력받은 N 번째 자리의 값이 T 일 때 N - 1번째 자리 값은 T ~ 9 까지이다.

전체코드 (top-down)

public class Main {

    static Long dp[][];
    static int mod = 10_007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Long[N + 1][10];


        //초기값 설정
        for(int i = 0; i <= 9; i++) {
            dp[1][i] = 1L;
        }


        long result = 0;

        for(int i = 0; i <= 9; i++) {
            result += recur(N, i);

        }
            System.out.println(result % mod);

    }

    static long recur(int digit, int val) {

        if (digit == 1) {
            return dp[digit][val];
        }

        if(dp[digit][val] == null) {
//            if (val == 9) {
//                dp[digit][val] = recur(digit - 1, 9) % mod;
//            } else {
//                long result = 0;
//                for(int i = val; i <= 9; i++) {
//                    result += recur(digit - 1, i);
//                }
//                dp[digit][val] = result  % mod;
//            }
            long result = 0;
            for(int i = val; i <= 9; i++) {
                result += recur(digit - 1, i);
            }

            dp[digit][val] = result % mod;
        }

        return dp[digit][val];
    }
}

코드 상세

• N을 입력받는다.
  • 입력받은 N + 1 크기의 이차원배열 생성
  • N + 1인 이유는 인덱스가 0 부터 시작하기 때문에
  • 두 번째 값이 10인 이유는 0~9까지 이기때문에

static Long dp[][];
static int mod = 10007;

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

dp = new Long[N + 1][10];

• 배열의 초기값을 설정한다.
  • 1자리 일 때 각각의 수는 1개만 가능하기 때문에

for(int i = 0; i <= 9; i++) {
    dp[1][i] = 1L;
}

• 재귀함수를 만든다.
  • 해당 함수에서는 digit [자릿수] 가 1 일 경우 dp[digit][val]를 리턴한다.
  • 배열 값이 초기화가 되어있지않다면 [== null] 값을 초기화 한다.
  • 위에서 얘기하였듯이 N번째 자리 val에 대하여 N - 1 자리 값은 val ~ 9 까지 이다.
    • 따라서 인자로 받은 val를 for의 초기값으로 설정하고 9 까지 for문을 돌면서 값을 저장한다.
  • 값을 저장할 때는 mod만큼 나누어 저장한다. 여기서는 모듈러 연산이 사용된다.

static long recur(int digit, int val) {
    if (digit == 1) {
        return dp[digit][val];
    }

    if(dp[digit][val] == null) {
        long result = 0;
        for(int i = val; i <= 9; i++) {
            result += recur(digit - 1, i);
        }

        dp[digit][val] = result % mod;
    }

    return dp[digit][val];
}

• 마지막으로 N번쨰 자리 0~ 9 까지 for문을 돌면서 결과를 구한다.
  • 0 ~ 9 까지 인 이유는 조건에 나와있다.

long result = 0;

for(int i = 0; i <= 9; i++) {
    result += recur(N, i);

}
    System.out.println(result% mod);

정리

이 문제에서는 손으로 적어보면서 쉽게 풀 수 있었을 것이다. 별 다른 예외없이 가장 앞부터 0~9를 채우고 자릿수를 하나씩 줄여가며 범위를 줄여나가면 쉽게 해결 할 수 있었을 것이다.