글 읽기 - 진짜 뭘까요..

jwl0105 2년 전 0

사실 이 문제를 보자마자 rgb거리 문제인가? 그 문제를 예전에 풀었던 방법이랑 매우 유사해서 금방 풀줄 알았습니다.

근데 반례랑 dp배열 모두 값이 똑바로 나오고 있는데 자꾸 틀렸습니다가 나와서 이유를 도대체 모르겠습니다..

dp배열이 이상하게 나오는것도 아니고 값을 똑바로 못 찾는것도 아닌거 같은데.. 정말 모르겠습니다 반례 부탁드리겠습니다..

#include <stdio.h>
int map[100001][3], dp[100001][3], size=0;
int getMax(int a, int b, int c) // 세 개 중 최댓값 찾는 함수
{
    int n=a;
    if(n<b)
    n=b;
    if(n<c)
    n=c;
    return n;
    
}
int getMin(int a, int b, int c)// 세 개 중 최솟값 찾는 함수
{
    int n=a;
    if(n>b)
    n=b;
    if(n>c)
    n=c;
    return n;
}
void find_max() // 하나씩 내려가면서 그 전 행의 최댓값을 찾아서 dp에 저장하는 함수
{
    for(int a=1; a<size; a++)
    {
        int temp=0;
        for(int b=0; b<3; b++)
        {
            if(b==0)
                dp[a][b]+=getMax(dp[a-1][0], dp[a-1][1], 0);
            else if(b==1)
                dp[a][b]+=getMax(dp[a-1][0], dp[a-1][1], dp[a-1][2]);
            else
                dp[a][b]+=getMax(0, dp[a-1][1], dp[a-1][2]);
        }
    }
}
void find_min()  // 하나씩 내려가면서 그 전 행의 최솟값을 찾아서 dp에 저장하는 함수
{
    for(int a=1; a<size; a++)
    {
        int temp=0;
        for(int b=0; b<3; b++)
        {
            if(b==0)
                dp[a][b]+=getMin(dp[a-1][0], dp[a-1][1], 10);
            else if(b==1)
                dp[a][b]+=getMin(dp[a-1][0], dp[a-1][1], dp[a-1][2]);
            else
                dp[a][b]+=getMin(10, dp[a-1][1], dp[a-1][2]);
        }
    }
}
void copy() // dp 배열에 기존 숫자를 받아서 최솟값 혹은 최댓값만 더해도 되게끔 했습니다.
{
    for(int a=0; a<size; a++)
        for(int b=0; b<3; b++)
            dp[a][b]=map[a][b];
}
int main()
{
    int ans=0;
    scanf("%d", &size);
    for(int i=0; i<size; i++)
    {
        for(int j=0; j<3; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    copy();
    find_max();
    ans=getMax(dp[size-1][0], dp[size-1][1], dp[size-1][2]);
    printf("%d ", ans);
    copy();
    find_min();
    ans=getMin(dp[size-1][0], dp[size-1][1], dp[size-1][2]);
    printf("%d", ans);
}

flyjb 2년 전 1

9 9 9

일때 최솟값이 잘못 나오네요

jwl0105 2년 전 1

감사합니다..!

틀린 이유가 각 배열인덱스에 올 수 있는 수의 범위가 0~9인거지 dp에 올 수 있는 값이 0~9인게 아닌데.. 제가 거길 착각했네요..

지적해주셔서 감사합니다!

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

문제

문제

출처

ICPC

진짜 뭘까요..

jwl0105 2년 전 0

flyjb 2년 전 1

jwl0105 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말