백준 11057번(오르막 수)

개요

[링크]백준 11057번: 오르막 수

• 입력
  첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

• 출력
  첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

접근 방식

이전에 풀었던 [백준 10844번(쉬운 계단 수)] 문제와 유사해서 비교적 쉽게 풀었다.

차이점이라면 쉬운 계단 수 문제는 first+1값과 first-1값만 더하면 되지만
이번 문제는 first값이 first+1부터 9일때까지 반복문을 이용해 더해야하고,
다음 단계에서 first값이 같을 수도 있으므로 같을 때의 값도 더해야한다.

또한 0으로 시작이 가능하므로 first값이 0부터 9일때를 다 더해야한다.

코드

#include<iostream>

//배열 최대값
const int MAX = 1000;
//나눌 값
const int MOD = 10'007;
using namespace std;
int dp[10][MAX],amount=0;

void input() {
	cin >> amount;
}


//앞자리 first일때, n번째부터 끝자리까지의 최댓값 
int solution(int first, int n)
{
	//만약 n이 끝 값이면 끝값부터 끝값의 오르막 수는 first값 하나이므로 1을 return
	if (n==amount-1) return 1;

	//ret값에 dp값 참조
	int& ret = dp[first][n];
	//이미 ret값 존재시 return ret
	if (ret != 0) return ret;

	//9보다 작은 값은  n+1부터 끝까지 범위면서 맨 앞 수가 first+1인 오르막수를 ret값에  추가로 더해준다,
	if (first < 9) {
		int temp = first;
		//하지만 오르막 수는 해당 first값부터 9까지 조사해야하므로 반복문을 이용해 추가로 더 조사한다.
		while (temp < 9) {
			ret += solution(temp + 1, n + 1);
			ret %= MOD;
			temp++;
		}
	}
	//first값과 같아도 오르막 수가 가능하므로  n+1부터 끝까지 범위면서 맨 앞 수가 first인 오르막 수를 ret값에 더해준다
	ret += solution(first, n + 1);
	ret %= MOD;

	return ret;
}

int main() {
	int sum = 0;
	input();
	for (int i = 0; i < 10; i++) {
		sum += solution(i,0);
		sum %= MOD;
	}
	cout << sum;

}

문풀후생

사실 아무생각없이 first값과 first+1일때의 값만
ret값에 더해주도록 구현했더니 예시 답이 터무니없이 작게나와서
고민하다가 반복문으로 9까지 더해야하는 사실을 깨달았다.

바로 전 문제와 똑같다는 생각에 나온 실수인것 같다.