글 읽기 - RGB 거리 질문입니다.

ljm6868 8년 전 0

안녕하세요. RGB 거리를 풀다가 궁금한 점이 있어서 올립니다.

저는 단순히 입력을 받으면 R,G,B 로 각각 시작하는 3가지 케이스를 나누어서

각 케이스마다 최단비용을 찾아 더한 후 최종적으로 3가지 경우를 비교해서

최저비용이 드는 것을 출력하도록 하였는데...

틀렸습니다가 떠서 제가 어떤 부분을 잘못생각하는지 궁금하네요...

조언 부탁드립니다.

#include<iostream>
using namespace std;

int street[1001][4];

int main(void) {
	int N, R, G, B, sum = 0, result = 99999, a, b, c;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> R >> G >> B;
		street[i][1] = R;
		street[i][2] = G;
		street[i][3] = B;
	}
	for (int j = 1; j <= 3; ++j) {
		sum += street[0][j];
		a = j;
		for (int i = 1; i < N; ++i) {
			if (a == 1) {
				b = 2;
				c = 3;
			}
			else if (a == 2) {
				b = 1;
				c = 3;
			}
			else{
				b = 1;
				c = 2;
			}
			if (street[i][b] > street[i][c]) {
				sum += street[i][c];
				a = c;
			}
			else {
				sum += street[i][b];
				a = b;
			}
		}
		result = result > sum ? sum : result;
		sum = 0;
	}
	cout << result << endl;
	return 0;
}

baactree 8년 전 0

지금 당장 최소 비용을 찾아서 그리디 하게 푸는게 아니라

모든 경우의 수를 따지는게 맞는 풀이 아닌가 싶네여

ljm6868 8년 전 0

아 문제를 잘못 생각했네요. 무조건 작은 경우만 생각하면 되는줄 알았는데, 큰 수로 가도 결국은 작아지는 경우도 있군요..

다시 생각해서 풀어보겠습니다~ 감사합니다!

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

문제

문제

출처

ICPC

RGB 거리 질문입니다.

ljm6868 8년 전 0

baactree 8년 전 0

ljm6868 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말