글 읽기 - 이 문제 계속 삑나는 이유가 뭘까요..ㅠㅠ

niceghp12 5년 전 0

문제를 보시면 알겠지만.. 굉장히 단순한 이차원 다이나믹인 것 같은데.. 계속 틀렸다고 나오네요.. ㅜㅜ

타 사이트에서 채점해 보니 627000을 출력해야 할 것을 630000으로 출력하는데.. 제 알고리즘에 무언가 패착이 있는가 봅니다

그 패착이 무엇인지, 또는 반례라도 아실 것 같은 분은 답변해주시면 정말 감사드리겠습니다!!

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MIN(a,b) ((a)<(b)?(a):(b))

int n;
int visit[1001]; // visit[i] = i번째 날에 리조트를 가는가?
int dp[1001][11]; // 메모이제이션 배열

int mincost(int day, int coupon) // day날에서 쿠폰 coupon개를 가지고 선택의 기로, 끝까지가는 최솟값
{
    int &ret = dp[day][coupon];

    if (ret != -1) return ret;
    else ret = 9999999;

    if (day > n) return ret = 0; // day날까지 전부다 갔다는 말이므로 끝.

    if (visit[day] == 0) ret = MIN(ret, mincost(day+1,coupon));

    if (coupon >= 3) ret = MIN(ret, mincost(day+1,coupon-3)); // 쿠폰 사용가능하면 써보는 경우 체크
    ret = MIN(ret, mincost(day+1,coupon)+10000);
    ret = MIN(ret, mincost(day+3,coupon+1)+25000);
    ret = MIN(ret, mincost(day+5,coupon+2)+37000);

    return ret;
}

int main()
{
    int k;
    int i,j;
    int tmp;

    memset(dp,-1,sizeof(dp));
    memset(visit,1,sizeof(visit));

    scanf("%d%d",&n,&k);

    for (i=0;i<k;i++) {
        scanf("%d",&tmp);
        visit[tmp] = 0;
    }

    printf("%d",mincost(1,0));
}

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

문제

문제

출처

ICPC

이 문제 계속 삑나는 이유가 뭘까요..ㅠㅠ

niceghp12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말