Today's Algorithm(2018-10-06)

boj 1003

피보나치 수열에 대해 이름을 모르실지 몰라도 규칙을 알면 기억 나시는 분들 많으실거에요. 그만큼 간단하고 단순한데요. 보통은 재귀를 이용하여 많이 구현합니다. 오늘은 가볍게 쉬운 문제를 풀고 싶어서 백준 문제 순위에서 쉬워보이는 문제를 찾았는데요. 앞 페이지에서 쉽게 찾을 수 있었습니다. 그만큼 많이 도전한 문제란 뜻이죠!

처음 이 문제를 보고 쉽겠다는 생각이 들었습니다. 애초에 피보나치 수열의 코드를 문제에서 제공했기 때문입니다. 근데 이를 이용해서 문제를 풀었는데 시간초과가 떴습니다... 다시 문제를 자세히 보니 제한시간이 0.25초 이더라구요. 따라서 재귀의 계산을 줄여야 했고 동적 계획법을 사용해야 했습니다.

제가 생각하는 동적 계획법은 과거에 계산했던 값을 저장해두고 이후에 그 값을 이용하여 중복되는 계산을 줄이는 것입니다. 이렇게 하기 위해선 기본적으로 전에 계산했던 값들을 저장할 배열과 값의 유무를 저장할 배열, 총 2개가 필요합니다. 경우에 따라 값을 저장한 배열을 이용하여 값의 유무까지 알 수도 있어 1개로도 가능합니다.

 

전 아래 코드와 같이 값이 없을 때 재귀를 이용하여 값을 구할 때까지 재귀가 될 수 있도록 하였습니다. 그리고 다음 계산에서 기존 값이 사용될 수 있도록 계산된 값은 배열에 넣어두었습니다. 다른 사람의 풀이를 보니 재귀를 이용하지 않고 처음부터 반복문 돌려 배열을 채워넣은 다음 그 배열의 값을 불러해결할 수도 있더라구요. 문제 자체가 단순해서 이렇게 더 쉽게 해결도 가능하네요!!

int d[41];
int zero[41];
int one[41];

void fibonacci(int n) {
    
    if(d[n-1] == 0) {
        fibonacci(n - 1);
    }
    if(d[n-2] == 0) {
        fibonacci(n - 2);
    }

    d[n] = 1;
    zero[n] = zero[n-1] + zero[n-2];
    one[n] = one[n-1] + one[n-2];
}

int main() {
    d[0] = 1, d[1] = 1, d[2] = 1;
    zero[0] = 1, zero[1] = 0, zero[2] = 1;
    one[0] = 0, one[1] = 1, one[2] = 1;

    int input;
    scanf("%d", &input);
    for(int i = 0 ; i < input; i++) {
        int temp;
        scanf("%d", &temp);
        if(temp > 2) {
            fibonacci(temp);
        }
        printf("%d %d\n", zero[temp], one[temp]);
    }
    return 0;
}