글 읽기 - 계단오르기문제 게시판 반례들도 넣어서 맞았는데 틀렸다고 뜹니다.

sohnryang 5년 전 0

어느 부분이 잘못된 걸까요..?

/*
 * Baekjoon Online Judge #2579
 * https://www.acmicpc.net/problem/2579
 */
 
#include <algorithm>
#include <cstdio>
#include <cstring>
 
using namespace std;

const int INF = 987654321;
int in_n, steps[301], cache[301][2];
 
int climb(int pos, int last_jump) {
    if (pos == in_n - 1) return steps[pos];
    if (pos >= in_n) return -INF;
    int &ret = cache[pos][last_jump];
    if (ret != - 1) return ret + steps[pos];
    if (last_jump != 1)
        ret = climb(pos + 1, 1);
    ret = max(ret, climb(pos + 2, 2));
    return ret + steps[pos];
}
 
int main() {
    scanf("%d", &in_n);
    memset(steps, -1, sizeof(steps));
    memset(cache, -1, sizeof(cache));
    for (int i = 0; i < in_n; ++i)
        scanf("%d", &steps[i]);
    printf("%d\n", max(climb(0, 0), climb(1, 2)));
    return 0;
}

sohnryang 5년 전 0

이 문제가 재귀적 DP가 안맞는걸까요?

djm03178 5년 전 0

last_jump가 2일 때, cache[x][last_jump]는 어떨까요?

sohnryang 5년 전 0

음 그거 생각해서 고쳐봤는데

sohnryang 5년 전 0

그래도 안되네요

/*
 * Baekjoon Online Judge #2579
 * https://www.acmicpc.net/problem/2579
 */
 
#include <algorithm>
#include <cstdio>
#include <cstring>
 
using namespace std;

const int INF = 987654321;
int in_n, steps[301], cache[301][2];
 
int climb(int pos, int last_jump) {
    if (pos == in_n - 1) return steps[pos];
    if (pos >= in_n) return -INF;
    int &ret = cache[pos][last_jump];
    if (ret != - 1) return ret + steps[pos];
    if (last_jump != 1)
        ret = climb(pos + 1, 1);
    ret = max(ret, climb(pos + 2, 2));
    return ret + steps[pos];
}
 
int main() {
    scanf("%d", &in_n);
    memset(steps, -1, sizeof(steps));
    memset(cache, -1, sizeof(cache));
    for (int i = 0; i < in_n; ++i)
        scanf("%d", &steps[i]);
    printf("%d\n", max(max(steps[0] + climb(1, 1), steps[0] + climb(2, 2)),
                       climb(1, 2)));
    return 0;
}

djm03178 5년 전 0

제 말씀은, cache의 1차원에는 인덱스가 0과 1밖에 없습니다. 그런데 cilmb(x, 2)가 호출되면 cache[x][2]에 접근하게 되므로 배열의 범위를 벗어납니다.

sohnryang 5년 전 0

last_jump를 last_jump - 1로 고쳤는데도 안되네요...

djm03178 5년 전 0

ret가 22번째 줄까지 실행된 후에도 -1로 남아있을 수 있는데 이 때 양수가 리턴되어버립니다.

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

문제

문제

출처

ICPC

계단오르기문제 게시판 반례들도 넣어서 맞았는데 틀렸다고 뜹니다.

sohnryang 5년 전 0

sohnryang 5년 전 0

djm03178 5년 전 0

sohnryang 5년 전 0

sohnryang 5년 전 0

djm03178 5년 전 0

sohnryang 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말