개요

[링크]백준 10844번: 쉬운 계단 수

• 입력
  첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

• 출력
  첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

접근 방식

• 첫번째 접근
  solution ( first, n ) 이렇게 함수를 세운 후,
  n번째부터 끝까지의 범위를 가지면서
  first값으로 시작하는 계단 수중에 최댓값을 반환하는 함수로 구현을 했다.

  if (first == 0)
  ret = solution(1, n + 1);
  	else if (first == 9)
  	ret = solution(8, n + 1);
  	else
  	{
  	ret = max(1 + solution(first+1, n + 1), 1 + solution(first - 1, n + 1));

  이런 식으로 first값이 0이면 1부터 시작하는 계단수 중 최대값을 저장하고,
  first값이 9면 8부터 시작하는 계단수 중 최대값을 저장하고,
  나머지는 first+1로 시작하는 계단수와 first-1로 시작하는 계단수 중에
  더 큰 값을 저장해주는 식으로 구현했다.

  1을 더한 이유는 n+1부터 끝까지의 계단수 중 최대 경우의 수에 경우의 수 하나 추가된다고 생각해서 1을 더했다.

  하지만 틀려서 계속 생각해보고 찾아보니,
  first+1, first-1 두 가지 중 하나의 경우만 존재하는 게 아니라
  당연히 둘 다 가능한 계단수이므로

  first+1부터 시작하는 계단수와 first-1부터 시작하는 계단수의 최댓값을
  비교해서 더 큰 값을 저장하는 게 아니라 두 값을 당연히 합쳐야 했다.
  

• 답안
  일단 1일 때, 9일 때, 둘 다 아닐때로 나눌 필요없이

  		//만약 first값이 0보다 클때 first-1으로 시작하고 n+1부터 끝까지의 최댓값 ret값에 더해줌
  		if (first > 0) {
  			ret += solution(first-1,n+1);
  			ret %= MOD;
  		}
  		//first값이 9보다 작을때 first+1로 시작하고 n+1부터 끝까지의 최대값을 ret에 더해줌
  		//if문을 두 번 씀으로써 자연스럽게 0과 9가 아닌값은 두번 통과하게되고, 0과 9는 한번씩 연산이 되게끔 한다.
  		if (first < 9) {
  			ret += solution(first + 1, n + 1);
  			ret %= MOD;
  		}

  이런 식으로 짠다면
  0인 값은 밑의 if문 한번 들어가고,
  9인 값은 위의 if문 한번 들어가고,
  나머지는 두번 다 들어가서 간편하게 구현 할 수 있다.

코드

#include<iostream>

//배열 최대값
const int MAX = 100;
//나눌 값
const int MOD = 1'000'000'000;
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;

	//만약 first값이 0보다 클때 first-1으로 시작하고 n+1부터 끝까지의 최댓값 ret값에 더해줌
	if (first > 0) {
		ret += solution(first-1,n+1);
		ret %= MOD;
	}
	//first값이 9보다 작을때 first+1로 시작하고 n+1부터 끝까지의 최대값을 ret에 더해줌
	//if문을 두 번 씀으로써 자연스럽게 0과 9가 아닌값은 두번 통과하게되고, 0과 9는 한번씩 연산이 되게끔 한다.
	if (first < 9) {
		ret += solution(first + 1, n + 1);
		ret %= MOD;
	}
	return ret;
}

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

}

문풀후생

solution함수를 main에서 호출할 때 n값을 0으로 준 걸 까먹고
if (n==amount) return 1;
조건을 이렇게 달았더니 값이 엄청 나와서 당황하고 한참 해멨다.
0부터 시작햇으면 amount-1에서 1을 반환해야 하는데
사소한 문제로 시간을 엄청 썼던 문제다.

레퍼런스

[링크] kks227님의 깃허브