Cooper's devlog

오르막수:11057번 - JAVA 본문

Algorithm/Baekjoon

오르막수:11057번 - JAVA

cooper_dev 2020. 7. 15. 01:52

1. 문제 링크

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

 

11057번: 오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수�

www.acmicpc.net

 

2. 문제 설명

3.문제 접근

-dp문제는 주로 규칙성을 찾고 점화식을 작성하는 것이 핵심이다!!

 

(1) 문제 규칙성을 확인하기 위해 표 작성!(표는 사랑이다)

 

[1] n = 1 -> 무조건 1개

0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1

 

[2] n = 2

0 1 2 3 4 5 6 7 8 9
10 9 8 7 6 5 4 3 2 1

 

 

[2] n = 3

0 1 2 3 4 5 6 7 8 9
55 45 36 28 21 15 10 6 2 1

 

 

0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1
10 9 8 7 6 5 4 3 2 1
55 45 36 28 21 15 10 6 2 1

→ 규칙성 : dp[3][3] = dp[2][3] + dp[3][4](위와 오른쪽의 합)

 

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
31
import java.util.Scanner;
 
public class inclining_num {
    
    static final int div = 10007;
    static int[][] dp;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        
        dp = new int[n+1][10];
        int sum = 0;
        
        for (int i = 0; i <= 9; i++)    dp[1][i] = 1;
        
        for (int row = 2; row <= n; row++) {
            for (int col = 9; col >= 0; col--) {
                if(col == 9)    dp[row][col] = 1;
                if(col <= 8)    dp[row][col] = (dp[row-1][col] + dp[row][col+1]) % div;
            }
        }
        
        for (int i = 0; i <= 9 ; i++) sum += dp[n][i] % div;
        
        System.out.println(sum % div);
        
        sc.close();
    }
}
 
  

 

<정답 확인>

5. 느낀점 또는 개선사항

 

(1)다른 규칙성을 가지고 있으나, 3차 반복문을 사용해야 하므로 시간복잡도(O^3) 효율적이지 못해 제외했다.

-> dp[i][j] = dp[i-1][j] + dp[i-1][j+1] .... + dp[i-1][9]

 

(2) dp문제는 규칙성을 찾아서 점화식을 작성하는 것이 제일 기본이라고 생각이 든다.

 

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

스티커:9465번 - JAVA  (0) 2020.07.16
RGB거리 : 1149번 - JAVA  (0) 2020.07.16
RGB거리 : 1149번 - JAVA  (0) 2020.07.15
1, 2, 3 더하기 3 : 15988 - JAVA  (0) 2020.07.13
합분해 : 2225번 - JAVA  (0) 2020.07.13
'Algorithm/Baekjoon' Related Articles more
Comments