[백준 DP] 11057번 - 오르막 수

11057번 - 오르막 수 

<문제>

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

11057번: 오르막 수

 

<문제 풀이>

점화식: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

마지막 자리수의 값을 기준으로 문제를 풀었다. 

3자리 숫자의 경우 

003, 013, 113, 023, 123, 223, 033, 133, 233, 333

이렇게 총 10가지의 오르막 수로 구성된다. 

바로 위의 풀이에서 볼 수 있듯이 마지막 수를 제외한 나머지 숫자의 경우의 수의 합으로도 원하는 값을 얻을 수 있다. 

점화식: dp[i][j] += dp[i - 1][k]

index에 사용된 변수의 개수에서도 알 수 있듯이 3중 for문을 사용해야 한다. 

 

<코드>

-> 2중 for문 사용 코드

#include <iostream>
#define MAX 1001
#define DIV 10007
using namespace std;

int N;
long long dp[MAX][10] = {0,};

int main() {
	cin >> N;

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

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0) {
				dp[i][j] = 1;
				continue;
			}
			dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
			dp[i][j] %= DIV;
		}
	}

	int sum = 0;
	for (int i = 0; i < 10; i++) {
		sum += dp[N][i];
	}

	cout << sum % DIV<< endl;

	return 0;
}

 

-> 3중 for문 사용 코드 

#include <iostream>
#define MAX 1001
#define DIV 10007
using namespace std;

int N;
long long dp[MAX][10] = { 0, };

int main() {
	cin >> N;

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

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0) {
				dp[i][j] = 1;
				continue;
			}
			
			for (int k = 0; k <= j; k++) {
				dp[i][j] += dp[i - 1][k];
			}
			dp[i][j] %= DIV;
		}
	}

	int sum = 0;
	for (int i = 0; i < 10; i++) {
		sum += dp[N][i];
	}

	cout << sum % DIV << endl;

	return 0;
}

 

<결과>

 

 

2022.12.22