글 읽기 - 구현 방법에 대해 조언 부탁드립니다

bnm6377 5년 전 0

구현하려고 한 방법은 먼저 색깔별로 cost를 다 저장해두고 최소비용을 누적시켜서 다음 cost를 갱신하도록 하였습니다.

예를 들면,

10 20 30

5 90 100

40 20 10

이렇게 입력받은 상태에서

cost[1][0]은 cost[0] 라인에서 자신과 동일한 색깔의 코스트를 제외한 두 개의 코스트 중 작은것의 합으로 갱신됩니다( 이 경우 20이 선택됩니다)

즉, cost[1][0] 은 5 -> 25로 변경됩니다.

같은 방법으로 cost[1][1] 을 구하면 90 -> 100 으로 변경되고, cost[1][2] 는 100 -> 110 으로 변경됩니다.

위 방법을 반복하면 최종적으로 코스트는

10 20 30

25 100 110

140 45 35

가 되고, 누적합이 젤 작은 35를 출력하고 종료하도록 구현했습니다.

이러한 구현방법이 잘못된 것인지 테스트 케이스를 만족해도 틀렸다고 나오네요. 어떻게 하면 좋을지 조언 부탁드립니다.ㅠ

import java.util.Scanner;

public class Main {
    int N;      // number of house
    long[][] cost;
    public static void main(String[] arg){
        Scanner scanner = new Scanner(System.in);
        Main rgbstreet = new Main();
        rgbstreet.N = scanner.nextInt();
        rgbstreet.cost = new long[rgbstreet.N][3];
        for(int i = 0  ; i < rgbstreet.N ; i++){
            for(int j = 0 ; j < 3 ; j++){
                rgbstreet.cost[i][j] = scanner.nextLong();
            }
        }
        long result = rgbstreet.getMinValue();
        System.out.print(result);
    }
    long getMinValue(){
        int i;
        for(i = 1 ; i < N ; i++){
            for(int j = 0 ; j < 3 ; j++){
                int v1 = (j+1)%3;
                int v2 = (j+2)%3;
                long min = cost[i-1][v1];
                if(cost[i-1][v2] < cost[i-1][v1])
                    min = cost[i-1][v2];
                cost[i][j] += min;
            }
        }
        long minimum = cost[N-1][0];
        for(int k = 0; k < 2 ; k++){
            if(cost[N-1][k] > cost[N-1][k+1])
                minimum = cost[N-1][k+1];
        }
        return minimum;
    }
}

bnm6377 5년 전 0

long[][] dp 배열을 만들어서 cost를 저장해나가며 최소값을 구하니 잘 되네요.. 동작 원리는 위 코드와 같은데 위 코드는 dp 배열을 사용하지 않고도 충분히 dp와 같은 기능을 수행한다고 생각되는데 왜 결과는 다르게 나올까요??..

tlatmdgus11 5년 전 1

시간이 좀 많이 지났지만 댓글 올립니다. 오늘 문제를 풀고, bnm6377님의 질문을 보았는데, 아무리 봐도 결과값을 구하는 코딩은 틀린점이 없었습니다. 하지만, 최소값을 구할 때 약간의 오해가 있었던 것으로 보입니다.

소스 33번째줄 if(cost[N-1][k] > cost[N-1][k+1]) 여기를 보시면

cost[N-1][ 0 ] > cost[N-1][ 1 ] 이고 cost[N-1][ 1 ] > cost[N-1][ 2 ] 는 최소값을 보장 못합니다.

단적인 예로

1 7 3

을 입력해보면, 최소값은 1이 아닌 3으로 출력이 되는 것을 보실 수 있으실 겁니다.

bnm6377 5년 전 0

아.. 그렇군요 그런 실수가 있었는데 전혀 모르고 있었습니다ㅠㅠ 덕분에 오랜 궁금증이 시원하게 해결되었습니다! 오래된 질문인데도 답변해주셔서 감사합니다!!

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

문제

문제

출처

ICPC

구현 방법에 대해 조언 부탁드립니다

bnm6377 5년 전 0

bnm6377 5년 전 0

tlatmdgus11 5년 전 1

bnm6377 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말