글 읽기 - c언어 반례 부탁드립니다..

gigohe2 2년 전 0

기존 RGB거리 문제에서 첫 집의 RGB값을 마지막 집까지 first인자로 가져가서

첫 집과 마지막 집에 칠해진 색이 같다면 아예 max를 넘게 만들었습니다.

모든 예제가 잘 작동하는데 반례가 있을까요?

#include <stdio.h>

int min(int a, int b)
{
    return a<b?a:b;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    int rgb[1002][3];
    typedef struct
    {
        int dp;
        int first;
    }DP;
    
    DP d[1002][3]={0,}; // 0 : R, 1 : G, 2 : B
    int tmp;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<3; j++)
        {
            scanf("%d", &rgb[i][j]);
            if(j==0)
            {
                tmp = d[i-1][1].dp < d[i-1][2].dp ? 1:2;
                d[i][j].dp = min( d[i-1][1].dp, d[i-1][2].dp) + rgb[i][j];
            }
            else if(j==1)
            {
                tmp = d[i-1][0].dp < d[i-1][2].dp ? 0:2;
                d[i][j].dp = min( d[i-1][0].dp, d[i-1][2].dp) + rgb[i][j];
            }
            else if(j==2)
            {
                tmp = d[i-1][0].dp < d[i-1][1].dp ? 0:1;
                d[i][j].dp = min( d[i-1][0].dp, d[i-1][1].dp) + rgb[i][j];
            }
            if( i==2 )
            {
                d[i][j].first = tmp;
            }
            else if( i>2)
            {
                d[i][j].first = d[i-1][tmp].first;
            }
            if(i==n)
            {
                if(d[i][j].first == j)
                {
                    d[i][j].dp=1000001; //만약 중복된다면 최댓값으로 만들어준다.
                }
            }
        }
    }
    int ans=1000005;
    for(int i=0; i<3; i++)
    {
        if(d[n][i].dp < ans)
        {
            ans = d[n][i].dp;
        }
    }
    printf("%d\n", ans);
    return 0;
}

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

문제

문제

출처

ICPC

c언어 반례 부탁드립니다..

gigohe2 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말