글 읽기 - 알고리즘에서 어디가 잘못된지 모르겠습니다.

dlgprbs9441 6년 전 0

2156번 문제에서

#include<stdio.h>

#define max(a,b) a>b ? a:b
int arr[100000];
int res[100000][3];

int main(){
    int N;
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        scanf("%d", arr + i);
    }
    
    res[0][0] = 0;
    res[0][1] = arr[0];
    res[0][2] = arr[0];
    
    for(int i=1; i<N; i++){
        res[i][0] = max(max(res[i-1][0], res[i-1][1]),res[i-1][2]);//포도주를 0개 연속으로 고른 경우
        res[i][1] = res[i-1][0] + arr[i];                          //포도주를 1개 연속으로 고른 경우
        res[i][2] = res[i-1][1] + arr[i];                          //포도주를 2개 연속으로 고른 경우
    }
    
    printf("%d", max(max(res[N-1][0], res[N-1][1]),res[N-1][2]));  //마지막 포도주를 고른 시점에서 
                                                                    //위 세 가지 경우중의 최대값을 출력한다.
}

sgchoi5 6년 전 1

질문하시기 전에 질문 검색 해보시면 볼 수 있는 내용이 많이 있습니다.

2 차원으로 안 하셔도 되고, dp[n] 의 의미를 n 까지 가장 많이 먹은 경우라고 보면

3 가지 중에 하나를 골라야 합니다.

n 번째를 안 먹는 경우: dp[n] = dp[n-1]

n 번째를 먹고 (n-1 번째 안 먹음) 가능한 이전의 최대치를 이용하는 경우: dp[n] = wine[i] + dp[n-2]

n 번째를 먹고 (n-1 번째 먹음) 가능한 이전의 최대치를 이용하는 경우: dp[n] = wine[i] + wine[i-1] + dp[n-3]

초기화를 적절히 해주고 i = 3 부터 시작해주면 됩니다..

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

문제

문제

출처

ICPC

알고리즘에서 어디가 잘못된지 모르겠습니다.

dlgprbs9441 6년 전 0

sgchoi5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말