11057 오르막 수

 

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

11057번: 오르막 수

 

동적 계획법을 잘 몰라서 아래 참고자료의 블로그를 참고했다.

 

문제에서 찾고자 하는 답을 다음과 같이 나타낼 수 있다.

a: 자리수

b: 끝자리

 

즉, a=2이고, b=1 이면

자리수가 2자리 이고, 1로 끝나는 오르막 수를 찾으면

01 11 로 2개가 나온다.

 

그럼 표에 나온 값들의 개수를 나타낸 표는 다음과 같다.

즉 위 표에서 즉, a=2이고, b=1 일 때, 01 11 로 값이 2개라서 아래의 표에서 2개를 나타내었다.

 

 

 

 

그런데 특징이 있다.

노란색으로 표시된 값들을 보면,

a=2, b=8 일때 값이 9 로 나타나 있는데,

이는 a=1일때 b=0,1,2,3,4,5,6,7,8 값들을 모두 더한 것이다.

즉 1+1+1+1+1+1+1+1+1=9 

 

이를 식으로 나타내면 

점화식 1) dp[n][i] = dp[n-1][0]+dp[n-1][1]+...+dp[n-1][i] 이다.

그런데, 이를 더 간단하게 나타낼 수 있다.

 

점화식 2) dp[n][i] = dp[n][i-1]+dp[n-1][i] 

(보라색으로 표시된 부분을 보면 알 수 있다.)

 

설명을 하자면

아래에 위치한 6의 값은

점화식 1)에서 설명한대로, 1+2+3 이다

 

그런데

1+2+3 중 1+2 는 점화식 1에서 설명한대로 (보라색 아래)3을 나타낸다.

 

때문에, 결과적으로

6 

= 1+2+3

=3(보라색 아래쪽) + 3(보라색 위쪽) 

 

때문에 두번째 점화식이 성립된다.

 

 

 

 

<최종 코드>

 

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

 
public class Main {
	
	
	
	public static void main(String[] args) throws IOException {
	
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int count[] =new int [N+1];
		int dp[][] = new int[N+1][10];
		
		for(int i=0; i<=9;i++) {
			dp[1][i]=1;
		}
		
		count[1]=10;
		
		for(int i=2;i<=N;i++) {
			for(int j=0;j<10;j++) {
				if(j==0) {
					dp[i][j]=1;
				}else {
				
				dp[i][j]=dp[i][j-1]+dp[i-1][j];
				dp[i][j]%=10007;
				}
				
				if(i==N) 	{
					count[i]+=dp[i][j];
					count[i]%=10007;
					
				}
			}
		}
		System.out.println(count[N]);

		}
		}

 

dp를

dp[][]=new int[N+1][10]로 만들어서,

아래 표처럼

위의 표에서 가로 a=0 부분이 추가된 상황으로 생각하면 된다.

 

 

dp[1][0]=dp[1][1]=dp[1][2] = ... =dp[1][9] = 1 이 당연하기에 초기화해주었고,

dp[1][0] = dp[2][0] = dp[3][0] = ..... =1 이다.

이것도 당연하기에 초기화 해줄 수 있다.

 

그 다음부터는 점화식 2) dp[n][i] = dp[n][i-1]+dp[n-1][i] 를 사용하여 

표를 채워주면 된다.

 

 

 

위 표의 값들을 더해서 count[] 값을 구할 수 있다.

즉,

count[1] = 1+1+1+1+1+1+1+1+1+1=10

count[2] = 1+2+3+4+5+6+7+8+9+10 = 55

...

 

 

 

 

 

참고 자료 :

https://maivve.tistory.com/67

(JAVA) 백준 11057번 : 오르막 수