어떤 문제인가?

메모이제이션을 이용해 재귀함수의 실행 속도를 늘리는 문제.

시행착오 횟수

2번

관찰

1. 값을 저장한 부분을 언제 참조하고, 언제 새로운 값을 넣을지 결정하는 게 관건이다.

1차 시도 : WA

지금 시간 기준으로 22일 전에 푼 거라, 어떤 생각으로 풀었는지 잘 생각나지 않는다. 다만 코드를 보면 기존 피보나치 수열을 풀 때와 비슷하게 접근하려다가 대차게 꼬인게 분명하다.

값을 1번만 저장하면 되는데, 다른 값이 여러 번 저장될 가능성이 너무 높았다.

#include <stdio.h>

int w(int a, int b, int c);
int S[21][21][21] = {{{0}}};

int w(int a, int b, int c) {
    if(a <= 0 || b <= 0 || c <= 0) {
        return 1;
    } if(a > 20 || b > 20 || c > 20) {
        return w(20, 20, 20);
    } if(a < b && b < c) {
        if(!S[a][b][c-1]) S[a][b][c-1]=w(a,b,c-1);
        if(!S[a][b-1][c-1]) S[a][b-1][c-1]=w(a,b-1,c-1);
        if(!S[a][b-1][c]) S[a][b-1][c] = w(a,b-1,c);
        return S[a][b][c-1]+S[a][b-1][c-1]-S[a][b-1][c];
    }
    if(!S[a-1][b][c]) S[a-1][b][c] = w(a-1,b,c);
    if(!S[a-1][b-1][c]) S[a-1][b-1][c] = w(a-1,b-1,c);
    if(!S[a-1][b][c-1]) S[a-1][b][c-1] = w(a-1,b,c-1);
    if(!S[a-1][b-1][c-1]) S[a-1][b-1][c-1] = w(a-1,b-1,c-1);
    return S[a-1][b][c] + S[a-1][b-1][c] + S[a-1][b][c-1] - S[a-1][b-1][c-1];
}

int main() {
    int a=0, b=0, c=0;
    while(a != -1 || b != -1 || c != -1) {
        scanf("%d %d %d", &a, &b, &c);
        printf("w(%d, %d, %d) = %d\n",a,b,c,w(a, b, c));
    }
    return 0;
}

2차 시도 : WA

문제를 잘 보니, $w(a,b,c)$에서

가 다음보다 우선시된다.

이를 고려하지 않아서 틀렸다.

3차 시도 : AC

2차 시도에서 놓친 부분을 잡아낸 결과, AC를 받았다.

#include <stdio.h>

int D[21][21][21];

int w(int a, int b, int c) {
	if(a<=0||b<=0||c<=0) a=b=c=0;
    if(a>20||b>20||c>20) a=b=c=20;
	if(D[a][b][c]) return D[a][b][c];
	if(a<=0||b<=0||c<=0) D[a][b][c]=1;
	else if(a<b&&b<c) D[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
	else D[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
	return D[a][b][c];
}

int main()
{
	int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    while(a!=-1||b!=-1||c!=-1) {
    	printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
    	scanf("%d%d%d",&a,&b,&c);
    }
}

다른 분들의 풀이

전체적인 흐름은 내 코드와 다를 게 없으므로 생략한다.

한줄평

그 당시에는 어떻게 생각했는지 모르겠는데, 평범한 동적 프로그래밍 문제였다.