백준 11057번 - 오르막 수

오르막 수

동적계획법을 사용하는 문제로써 백준에서는 대표적인 문제이다.

동적계획법을 풀 때는 보통
반복문으로 밑에서부터 쌓아올리는 bottom-up 방식과
일단 재귀를 통해 부채를 쌓아두고 천천히 갚아나가는? 것 같은 top-down 형식 중 하나를 고르게 되는데

이 둘 중에서는 아무래도 bottom-up 방식이 난도가 더 있다고 평가되는 편이다. 점화식을 잘 짜기가 정말 어렵다.

그렇지만 이 문제는 실버급 난이도에 걸맞게
나름 점화식을 짜기 쉽다.
나름 조건도 평이한 수준이다.

중요한건

1. 목표로 하는 수의 길이
2. 직전 수

가 이 문제를 푸는 핵심이고 이걸 바탕을 점화식을 짜면 된다.
i가 현재 수의 길이, j가 마지막 자리의 숫자 라고 했을때

for(int k=0;k<=j;k++){
	dp[i][j] +=dp[i-1][k]
}

정도로 점화식을 쓸 수 있다 .(시그마 넣었다가 여기서 인식을 못하길래 코드로 변경)

또한, 답을 10007로 나눈 나머지를 요구하는데
mod연산에 대해 모른다면 알아두는 것이 좋다.
( a + b ) mod c = ( (a mod c) + (b mod c) ) mod c

전체 정답 코드는 다음과 같다.

#include<iostream>
#include<string>
using namespace std;
int dp[1001][10]={0};
int main(){
	int n;
	cin>>n;
	for(int i=0;i<=9;i++){
		dp[1][i]=1;
	}
	for(int i=2;i<=n;i++){
		for(int j=0;j<=9;j++){
			for(int k=0;k<=j;k++){
				dp[i][j]=(dp[i][j]%10007)+(dp[i-1][k]%10007);
			}
			dp[i][j]%=10007;
		}
	}
	int ans = 0;
	for(int i=0;i<=9;i++){
		ans=(ans%10007)+(dp[n][i]%10007);
	}
	cout<<ans%10007<<'\n';
}