[BOJ-11057] 오르막수

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

11057번: 오르막 수

---

[풀이]

 

dp[1][0] : 1자리수, 1번째 자리수 숫자가 0일때

dp[2][3] : 2자리수, 2번째 자리수 숫자가 3일때

 

dp[N][i] : N자리수, N번째 자리수 숫자가 i일때(i=0,1,2,3,4,5,6,7,8,9)

 

N번째 자리수가 i인 오르막수를 만들려면

N-1번째 자리 숫자가 0,1,2,..., i-1, i 인 오르막수인 경우에 가능하다.

 

점화식을 세워보면

dp[N][i] = dp[N-1][0]+ dp[N-1][1] + dp[N-1][2] + ...  + dp[N-1][i-1] + dp[N-1][i]

 

점화식을 봐도 잘 이해가 안간다면 아래의 예시를 살펴보자

 

(1) 자리수가 1인경우 오르막수: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

(2) 두자리수 이상인(자리수가 2이상인)경우 오르막수

2번째 자리수가 0인경우: 1번째 자리수가 0보다 작거나 같은 수여야한다. 00

2번째 자리수가 1인경우: 1번째 자리수가 1보다 작거나 같은 수여야한다. 01, 11

2번째 자리수가 2인경우: 1번째 자리수가 2보다 작거나 같은 수여야한다. 02, 12, 22

 

3번째 자리수가 0인경우: 2번째 자리수가 0보다 작거나 같은 수여야한다.  000

3번째 자리수가 1인경우: 2번째 자리수가 1보다 작거나 같은 수여야한다.  001 011 111

---

[ 코드(.py) ]

# -*- coding : utf-8 -*-
import sys
def main():
    N= int(sys.stdin.readline())
    dp=[[0]*10 for _ in range(N)]
    
    # 한자리수 오르막수 초기화
    for i in range(10):
        dp[0][i]=1

    # dp[i][j]= dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1]+dp[i-1][j]
    # (i+1)자리수가 j(0,1,2,...,9)인경우, 오르막수
    # (i)자리수가 j보다 작거나 같은것을 구한다.
    for i in range(1,N):#i: 자리수
        for j in range(10):#j=0,1,2,..,9
            for k in range(j+1):#k=0,1,2,...,j
                dp[i][j]+=dp[i-1][k]
    print(sum(dp[N-1])%10007)
    del dp
    
if __name__=='__main__':
    main()

---

[ 코드 (.java) ]

import java.util.Scanner;

public class Main11057 {
	static int N;
	static int dp[][];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N= sc.nextInt();
		dp=new int[N][10];
		
		//1자리수 초기화
		for(int i=0; i<10; i++)
			dp[0][i]=1;
		
		for(int i=1; i<N; i++) //2자리수 이상.
		{
			for(int j=0; j<10; j++) 
			{
				for(int k=0; k<=j; k++)
					dp[i][j]+=dp[i-1][k];
				dp[i][j]%=10007;
			}			
		}
		
		int result=0;
		for(int i=0;i<10; i++)
			result+=dp[N-1][i];
		System.out.println(result%10007);
	}
}