[백준/C++] 10844 쉬운 계단 수 (S1)

유형	난이도	완료일	링크	특이사항
DP	실버1	23/02/23	https://www.acmicpc.net/problem/10844

 

 

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[101][10];
int k = 1000000000;

int main(void)
{
	
	int n;
	cin >> n;
	
	for(int i= 1; i<10; i++)
	{
		arr[1][i] = 1;	
	}

	for(int i=2; i<=n; i++)
	{
		for(int j= 0; j<10; j++)
		{
			if(j==0)
				arr[i][j] = arr[i-1][1] %k;
					
			else if(j==9)
				arr[i][j] = arr[i-1][8] %k;
			
			else
				arr[i][j] = (arr[i-1][j-1]%k + arr[i-1][j+1]%k) % k ;
		}
	}
	
	long long sum = 0;
	
	for(int i= 0; i< 10; i++)
		sum += arr[n][i];
	
	sum = sum%k;
	
	cout << sum;
}

처음엔 숫자가 몇 자리인지, 즉 N의 값에 따라 달라지는 답의 규칙을 찾으려고 시도했다.

하지만 N이 4일 때 까지는 경우의 수가 61개로 직접 그려보면서 찾을 만 했으나 N=5 이상부터는 직접 찾을 수가 없었다. N=4까지 적용되는, 근거 없는 추론으로 S(n) = S(n-1)*2-n 이라는 식을 세워 시도해봤으나 역시 오답이었다.

그 후로도 N=2일 때와 N=3일 때의 겹치는 부분을 생각해보고 무슨 규칙이 있을까 계속 고민했지만 앞자리가 0일 땐 뒷자리에 오직 1만, 9일 때는 8만이 올 수 있다는 사실이 계속 걸렸다. 이 점 때문에 단순하게 이전 경우의 수 * 2 를 못했기 때문이다.

그래서 이 문제 덩어리인 0과 9를 어떻게 해결할지 생각했다. 우선 0과 9가 N에 따라서 개수가 어떻게 변하는지 찾으려 시도했다. 0과 9의 개수 변화를 알아내면 그것을 적용해 N과 N-1 사이의 규칙을 찾을 수 있을 것이라 기대했다. 그것을 추적하다 보니 0은 n-1의 1의 개수에 따라, 9는 n-1의 8의 개수에 따라 정해지고 다시 1과 8은 n-2의 0,2의 합과 7,9의 합으로 정해진 다는 사실이 그려졌다.

결국 n-1의 i-1과 i+1이 n의 i개수라는 사실을 생각하자 그냥 각 자릿수마다(n의 값에 따라) 0~9의 개수가 몇 개인지 기록하면 해결할 수 있다는 것을 깨달았다.

문제를 해결하는 방식이 주먹구구식으로, 모든 경우를 시도해보다가 우연으로 풀었다기 보다는 내 풀이 계획을 방해하는 요소를 해결하는 과정에서 풀이법을 발견한 방식이어서 만족스러웠다.