[JAVA 28] 11057. 오르막 수

11057. 오르막 수 (S1)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1  초	256  MB	57837	28391	22054	47.795 %

 

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

 

---

 

summary

오르막 수의 개수를 구하기

 

• 인접한 수가 같아도 오름차순
• 10,007로 나눈 나머지를 출력
• 수는 0으로 시작 가능

 

strategy

DP (경우의 수가 많음, 이전의 구한 값 활용 가능) 

 

• 자리수를 늘릴 때 새로운 숫자를 앞자리에 추가한다고 생각 
  • N=3 에서 0은 뒤에 0으로 시작하는 두자리수(N=2), 1로 시작하는 두자리수(N=2), ... 9로 시작하는 두자리수 (N=2) 모두 가능하다.
  • N=3 에서 1은 뒤에 1로 시작하는 두자리수(N=2), 2로 시작하는 두자리수(N=2) ... 9로 시작하는 두자리수 (N=2) 모두 가능하다.
• 각 자리수마다 0 ~ 9 를 추가하는 경우의 수를 각각 기록 (DP[자리수][0~9]) 
• int 범위를 넘어가기 때문에 모듈러 연산 활용( % 10007)

 

note

• 1 ≤ N ≤ 1,000

import java.io.*;
import java.util.*;

public class Main {
    
    static int N;
    static int[][] DP; 
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        DP = new int[N][10];

        for(int k = 0; k < 10; k++) DP[0][k] = 1;

        for(int n = 1; n < N; n++) {
            for(int k = 0; k < 10; k++) { // 각 자리마다 0~9 추가가
                for(int l = k; l < 10; l++) {
                    DP[n][k] += DP[n-1][l];
                    DP[n][k] %= 10007;
                }
            }
        }

        int sum = 0;
        for(int k = 0; k < 10; k++) sum += DP[N-1][k]; // N 자리수 경우의 수 합산

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

 

문제	결과	메모리	시간	언어코드	길이
11057	맞았습니다!!	14416 KB	100 ms	Java 11 / 수정	831 B

 

memo

• DP 는 2차배열을 일단 떠올려보자