알고리즘: 백준 11057번 오르막 수 (feat. c++)

백준 11057 링크입니다.

11057번: 오르막 수

 

다이나믹 프로그래밍을 이용하면 쉽지만 

 

어떤 구조를 이용하면 좋을지가 가장 어렵다.

 

dp를 이차원리스트로 해서 

 

dp[i][j] = 길이가 i인 끝자리수가 j인 오르막 수

 

라고 하면 쉽게 해결할 수 있다.  (끝자리수를 기준으로 나누는게 포인트)

 

i는 1 ~ 1000

j는 0 ~ 9까지 가능하다 

 

 

 

예를 들어 dp[2][3]을 구한다고 하면 

 

dp[2][3] = dp[1][2] + dp[1][1] + dp[1][0]

 

로 구성되어 있기 때문에 이를 코딩으로 나타내면 3중 for문이 된다. 

 

 

#include<iostream>
#include<stdlib.h>
using namespace std;

int main() {

	int N;  // 수의 길이 

	scanf("%d", &N);

	int dp[1001][10] = {0};  // 다이나믹 프로그래밍!

	for (int i = 0; i <= 9; i++) // 길이가 1인 수를 모두 1로 초기화한다. 
		dp[1][i] = 1;


	for (int i = 2; i <= N; i++)   // 길이 2부터 N까지 반복 
		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 total = 0;
    
	for (int i = 0; i < 10; i++)
	{
		total += dp[N][i];
	}
	printf("%d", total%10007);
	

	return 0;
}

 

 

다이나믹 프로그래밍을 사용해야 할 것 같다는 느낌은 있었지만 어떤식으로 

 

프로그래밍을 짜야할지 고민을 많이 하였다.  

 

세부적으로 나눠서 생각하는 습관을 들이면 좀 더 빠르고 정확하게

 

프로그래밍을 할 수 있을 것이다.