글 읽기 - 제 생각이 틀린 이유를 잘 모르겠습니다.

jwl0105 2년 전 0

말 그대로 입니다. 아무리 생각을 해봐도 틀린 이유를 진짜 모르겠습니다.

제가 생각한 방법은

자두가 떨어지는 시간과 자리를 바뀌는 횟수마다 가질 수 있는 최대 자두의 수를 구하는 dp 이차원 배열을 만드는 것 입니다.

dp[change][timer] 라고 하겠습니다.

dp[0][_]에는 자리를 한번도 바꾸지 않은 경우이니깐 자두가 1번에서 떨어질때 수를 하나씩 더하면 됩니다.

dp[i][j] (i, j>=1)는 그 전 들의 인덱스를 잘 확인하면서 각각의 경우에 대한 최댓값을 찾으면 된다고 생각합니다.

(dp[i][j]는 자리를 i번 바꾸는 경우, j초 이후 가질 수 있는 자두 개수의 최댓값입니다.)

물론 틀렸겠지만..혹시 이유를 아시는 분은 조언 혹은 지적 부탁드리겠습니다..

#include<stdio.h>
int dp[31][1001], plum[31], timer=0, change=0;
int find_max(int a, int b) {if(a>b) return a; return b;}
void fill_dp()
{
    for(int i=1; i<=timer; i++) // 자리를 한번도 바꾸지 않는 경우, 1일때만 카운트
    {
        if(plum[i]==1) 
        dp[0][i]=dp[0][i-1]+1;
        else // 자두가 2에서 떨어질때, 기존 값 가져오기
        dp[0][i]=dp[0][i-1];
    }
    for(int j=1; j<=change; j++)
    {
        dp[j][1]=1; // 자리를 한번이라도 바꾸는 경우 첫번째 경우는 무조건 먹을 수 있음
    }
    for(int a=1; a<=change; a++)
    {
        for(int b=2; b<=timer; b++)
        {
            if(a%2==1) // 자리를 바꾸는 횟수가 홀수인 경우 (마무리가 2번에서)
            {
                if(plum[b]==2) // 자두가 2번에서 떨어지는 경우
                dp[a][b]=find_max(dp[a-1][b-1], dp[a][b-1])+1;
                else // 1번에서 떨어지는 경우, 
                dp[a][b]=find_max(dp[a-1][b-1]+1, dp[a][b-1]); 
            }
            else
            {
                if(plum[b]==1)
                dp[a][b]=find_max(dp[a-1][b-1], dp[a][b-1])+1;
                else
                dp[a][b]=find_max(dp[a-1][b-1]+1, dp[a][b-1]);
            }
        }
    }
}
int main()
{
    scanf("%d %d", &timer, &change);
    for(int i=1; i<=timer; i++)
    scanf("%d", &plum[i]);
    fill_dp();
    printf("%d", dp[change][timer]);
}

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

문제

문제

출처

ICPC

제 생각이 틀린 이유를 잘 모르겠습니다.

jwl0105 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말