글 읽기 - 틀렸습니다 유형입니다.

uvzone 4년 전 0

나름 질문글 2년전꺼까지 다 읽어보면서 반례찾아보려 했지만 틀렸습니다가 계속떠서 조심스럽게 질문드립니다.

제가 생각한 원리는 피보나치 수열 원리에 의해서

n에서 0이 나오는 횟수 = n-1에서 0이 나오는 횟수 + n-2에서 0이 나오는 횟수

n에서 1이 나오는 횟수 = n-1에서 1이 나오는 횟수 + n-2에서 1이 나오는 횟수

라는 원리를 기반으로 코드를 작성하였고, 메모이제이션과 bottom-up방식을 채택했다고 생각했습니다... 혹시 제 생각이 틀렸나요?

출력이 틀린 예가 있어서 알려주시면 정말 감사하겠고 정말 죄송합니다...

*타임헤더 및 프로그램 시간측정은 빼고 채점했습니다(주석이라 영향도 없구요)

#include <stdio.h>
//#include <time.h>

int last_idx;
int count_0[41] = {
    1,
    0,
};
int count_1[41] = {
    0,
    1,
};

void count_num(int num)
{
    int i;
    if (num > 1)
    {
        if (last_idx < num)
        {
            for (i = last_idx + 1; i <= num; i++)
            {
                count_0[i] = count_0[i - 1] + count_0[i - 2];
                count_1[i] = count_1[i - 1] + count_1[i - 2];
            }
            last_idx = i;
        }
    }
}

int main(void)
{

    //clock_t start, end;
    //start = clock();
    int num, test_case;
    scanf("%d", &test_case);
    last_idx = 1;

    for (int i = 0; i < test_case; i++)
    {
        scanf("%d", &num);
        count_num(num);
        printf("%d %d\n", count_0[num], count_1[num]);
    }
    //end = clock();
    //printf("time : %lf", (double)((end - start)));

    return 0;
}

rhdqor213 4년 전 1

2 2 3 과 같은 입력이 들어오면 먼저 count_num(2); 가 실행되고, last_idx의 값은 3이 됩니다.

그 후 count_num(3);이 실행되면 19번째 줄의 if문에 튕기게 되고, count_0[3], count_1[3]은 계산한 적이 없으니 0 0이 출력되어 틀리게 되는 것이죠.

uvzone 4년 전 0

말도안되는 실수를 했었네용 ㅎㅎ... 감사합니당

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀렸습니다 유형입니다.

uvzone 4년 전 0

rhdqor213 4년 전 1

uvzone 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말