어떤 문제인가?

메모이제이션이든, 타뷸레이션이든 미리 배열에 수를 기록해 시간 내로 값을 구하는 문제.

시행착오 횟수

1번

관찰

1. 패턴이 반복되는 부분이 있다. 이를 이용하면 관계식을 세울 수 있다.

1차 시도 : WA

공책에 DP 점화식을 유도하다가, 어쩌면 갯수를 나타내는 일반항을 나타낼 수 있을지 모른다는 생각이 들었다.

다음은 그런 생각에서 나온 잘못된 일반항이다.

2시간에 걸친 삽질 끝에, 이 수열이 계차수열이 아님을 확인한 후에야 단념했다. 섣불리 공차가 있을 것이라 단정한게 실수였다.

2차 시도 : AC

다행히도 1차 시도를 하기 전에 이미 DP 점화식 구상은 끝난 상태였다. 규칙은 다음과 같다.

$D_{ij}$는 길이가 $i$이고 맨 처음 오는 수가 $j$일 때의 계단 수 개수이다.
이때 $i\geq 1$이며, $i=$일때 $0\leq j \leq 9$ 범위 내에서, $D_{ij}=1$ 이다.

범위에 0이 들어가서 의아해할수도 있는데, 1010 처럼 중간에 0이 들어간 경우도 고려하기 위함이다.
코드로 나타낸 결과는 다음과 같다.

#include <stdio.h>
#define LIM 1000000000

unsigned D[101][10];

int main()
{
	unsigned N, i, j,c=0;
	scanf("%d", &N);
	for (i=0; i<10;i++)
		D[0][i] = 1;
	for (i=1; i<=N;i++)
	{
		for (j = 0; j < 10; j++)
		{
			if (j < 1)
				D[i][j] = D[i - 1][j + 1] % LIM;
			else if (j > 8)
				D[i][j] = D[i - 1][j - 1] % LIM;
			else
				D[i][j] = (D[i - 1][j - 1] + D[i - 1][j + 1]) % LIM;
		}
	}
	for(i=1;i<10;i++) c=(c+D[N-1][i])%LIM;
	printf("%u",c);
}

다른 분들의 풀이

내가 찾는데 실패한 수열 일반항을 찾은 것 같은 분이 계신다.

__int128 i=5,d[101]={1e9,9,17,32,61,116};main(n){for(scanf("%d",&n);i++<n;)d[i]=d[i-1]+4*d[i-2]-3*d[i-3]-3*d[i-4]+d[i-5];printf("%d",d[n]%*d);}

wisqa님의 소스
-> https://www.acmicpc.net/source/6759380

사실 일반항이라 보기에는 애매하지만, 굉장히 특이한 풀이 방식이라 올리고자 한다. 나중에 시간이 날 때 한번 분석해봐야겠다.

한줄평

섣부른 단정, 끝없는 삽질의 지름길.
앞으로 문제를 풀 땐 확실하게 확인하고 풀겠다.