[백준 C++] 11057번: 오르막 수

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

 

dp를 사용하여 푼 문제

 

끝자리의 숫자에 따라 오르막수의 수를 따로 배열에 저장해주었다.

 

따라서 dp[1001][10] 다차원 배열을 선언해준뒤

1의 자리의 경우 0이 앞에 있는것을 허용하므로 dp[0][0~9]까지 1을 넣어준다. 

 

또한 dp[1][0] 의 경우 오르막수가 되려면 앞자리가 0인 경우밬에 없으므로 dp[0][0]값만 넣어주고

 

dp[1][1]의 경우 오르막수가 되려면 앞자리가 0과 1인경우이므로 dp[0][0] 과 dp[0][1]을 넣어준다. 삼중 for문을 이용하여 이를 구현해주었다.

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

예제는 모두 맞혔지만 시간초과가 아닌 문제를 틀렸고 이유를 찾았다.

 

dp[i][j] += (dp[i - 1][k]) % MODULER;

 

이 줄을 살펴 보면 moduler가 저 하나의 값에만 나누어주는것을 볼수 있다. 따라서 코드를 

 

dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MODULER;

 

이런식으로 바꿔주었다. 

 

전체코드는

 

#include <iostream>
#include <algorithm>
#define MODULER 10007
using namespace std;
int dp[1001][10] = { 0, };
 
int main(int argc, char* argv[])
{
	int n;
	cin >> n;
 
	for (int i = 0; i <= 9; i++) {
		dp[0][i] = 1;
	}
 
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k <= j; k++) {
				dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MODULER;
			}
		}
	}
 
	for (int i = 0; i <= 9; i++) {
		dp[n][0] = (dp[n][0] + dp[n - 1][i]) % MODULER;
	}
 
	cout << dp[n][0] << '\n';
 
	return 0;
}

 

좀 더 감이 잡힌다.