메모가 줄인 호출 횟수

시간 제한: 1000 ms메모리 제한: 256 MBSilver V3작성자: 관리자

문제

연준은 1칸 또는 2칸으로 $n$ 칸 계단을 오르는 방법의 수를 세는 두 함수가 각각 몇 번 호출되는지 비교한다. f1은 메모가 없고 f2는 메모를 사용한다. 두 함수 모두 첫 줄에서 호출 횟수를 1 증가시킨다.

int f1(int c) {            // 메모 없음
    cnt1++;
    if (c > n) return 0;
    if (c == n) return 1;
    return f1(c + 1) + f1(c + 2);
}

int f2(int c) {            // 메모 사용, memo는 처음에 모두 -1
    cnt2++;
    if (c > n) return 0;
    if (c == n) return 1;
    if (memo[c] != )  memo[c];
     memo[c] = f2(c + ) + f2(c + );
}

문제 통계

전체 제출

정답

100%

정답률

정답자 수

int f1(int c) { // 메모 없음 cnt1++; if (c > n) return 0; if (c == n) return 1; return f1(c + 1) + f1(c + 2); } int f2(int c) { // 메모 사용, memo는 처음에 모두 -1 cnt2++; if (c > n) return 0; if (c == n) return 1; if (memo[c] != ) memo[c]; memo[c] = f2(c + ) + f2(c + ); }

메모가 줄인 호출 횟수

문제

메모가 줄인 호출 횟수

문제

제한

입출력 예시