글 읽기 - c언어 시간초과 및 점화식이 맞는지...

dltjr0703 2년 전 0

~~전에 계단 오르기 문제에서 변형해서 풀다보니 stair라고 이름 지은건 신경쓰지 마세요~~

일단 제출하면 시간초과납니다.

그래서 이 코드가 시간 초과만 아니면 옳은건지도 잘 모르겠습니다.

제가 생각한 점화식은

dp[n] = max(dp[n-3]+stair[n]+stair[n-1],

dp[n-2]+stair[n],

dp[n-1])

입니다.

시간 초과를 해결할 방법과 점화식이 옳은지 궁금합니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

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

int dp[301]={0,};
int stair[301]={0,};

int main(){
    int n, a, i;
    scanf("%d", &n);
    for (i = 1; i<=n; i++){
        scanf("%d", &a);
        stair[i] = a;
    }
    
    dp[1] = stair[1];
    dp[2] = stair[1]+stair[2];
    
    for (i = 3; i<=n; i++){
        if (stair[i]!=0){
            dp[i] = max(max(dp[i-3]+stair[i-1]+stair[i],
                        dp[i-2]+stair[i]),
                        dp[i-1]
                        );
        }
        else{
            dp[i] = dp[i-1];
        }
        //printf("%d : %d ? %d\n", i, dp[i-3]+stair[i-1]+stair[i],dp[i-2]+stair[i]);
    }
    printf("%d", dp[n]);
    

}

djm03178 2년 전 1

이 코드가 시간 초과 나는 이유는 비효율적이기 때문이 아니라 배열의 범위를 벗어나는 undefined behavior가 발생하기 때문입니다.

n의 최댓값이 10000인데, 이 코드에서 사용하는 배열의 크기는 겨우 301밖에 안 되고 있습니다.

djm03178 2년 전 1

계단 오르기 문제를 변형하셔서 신경쓰지 말라고 하셨지만, 바로 그 부분을 신경쓰지 않으셔서 발생한 문제입니다.

dltjr0703 2년 전 0

진짜 어이없는 이유엿네요...

제가 직접 0을 9000개 정도 넣었을때도 프로그램이 1초 안에 정상 종료해서

뭐가 문제지 하고있었는데...하하

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

문제

문제

출처

ICPC

c언어 시간초과 및 점화식이 맞는지...

dltjr0703 2년 전 0

djm03178 2년 전 1

djm03178 2년 전 1

dltjr0703 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말