글 읽기 - 게시판에 있는 반례를 왠만큼 돌려봤는데 틀리는 이유를 모르겠습니다.

kadragon 4년 전 0

한 칸 올라갈때와, 두 칸 올라갈때를 각각 따로 생각하는 재귀함수를 구현하였습니다.

시간초과를 피하기 위해서, 한 칸 올라왔을때, 두 칸 올라와서 왔을때, 점수도 비교하였구요.

왠만한 반례들을 돌려보았는데 어떤부분에 오답처리 되는지 도움을 요청합니다.

// https://www.acmicpc.net/problem/2579
// 계단 오르기

#define max(a, b) ((a) > (b) ? (a) : (b))

#include <stdio.h>

int n, m = 0;
int arr[301];
int v[301][2];

void floor(int i, int sum, int one) {
    if (v[i][one] < sum)
        v[i][one] = sum;
    else
        return;

    if (n == i) {
        m = max(m, sum);
        return;
    }

    if (one < 1)
        floor(i + 1, sum + arr[i + 1], 1);
    if (i + 2 <= n)
        floor(i + 2, sum + arr[i + 2], 0);
}


int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);

    floor(1, arr[1], 0);

    printf("%d", m);

    return 0;
}

ho94949 4년 전 2

첫 번째 계단을 안 밟는게 이득일 수 있습니다.

kadragon 4년 전 0

첫 번째 계단은 반드시 밟아야 하는줄 알았네요. 감사합니다.

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

문제

문제

출처

ICPC

게시판에 있는 반례를 왠만큼 돌려봤는데 틀리는 이유를 모르겠습니다.

kadragon 4년 전 0

ho94949 4년 전 2

kadragon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말