글 읽기 - RGB문제 어디서 틀렸을까요..?

lennie 7년 전 0

그리디 방식으론 안된다는걸 깨닫고 빨,초,파 각각의 경우마다 집의 개수만큼 반복하여 최소한의 비용을 구하였습니다.

즉 결국 세 가지 비용 값이 나오게 되고 이 중 최소값을 리턴하는 방식으로 알고리즘을 짰는데..

제 알고리즘이 틀렸을까요? 아니면 구현상의 문제일까요?

웬만한 테스트 케이스는 모두 만족하긴 합니다..

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char const *argv[])
{
	int houses[1001][3];
	int length;
	scanf("%d" , &length);
	for ( int i = 0 ; i < length ; i ++ ) {
		scanf("%d" , &houses[i][0]);
		scanf("%d" , &houses[i][1]);
		scanf("%d" , &houses[i][2]);
	}
	int previous;
	int min;
	vector<int> minimums (0);
	for ( int i = 0 ; i < 3 ; i ++ ) {

		previous = i;
		minimums.push_back(houses[0][i]);

		for ( int j = 1 ; j < length ; j ++ ) {
			if ( previous == 0 ) {
				if ( houses[j][1] < houses[j][2] ) {
					previous = 1;
					minimums[i] += houses[j][1];
				}
				else{
					previous = 2;
					minimums[i] += houses[j][2];
				}
			}

			else if ( previous == 2) {
				if ( houses[j][0] < houses[j][1] ) {
					previous = 0;
					minimums[i] += houses[j][0];
				}
				else{
					previous = 1;
					minimums[i] += houses[j][1];
				}
			}
			
			else if ( previous == 1) {
				if ( houses[j][0] < houses[j][2] ) {
					previous = 0;
					minimums[i] += houses[j][0];
				}
				else{
					previous = 2;
					minimums[i] += houses[j][2];
				}
			}

		}
	}

	min = minimums[0];
	for ( int i = 0 ; i < minimums.size() ; i ++ ) {
		if ( min > minimums[i] ) {
			min = minimums[i];
		}
	}
	printf("%d" , min);
	return 0;
}

imgosari 7년 전 0

전 이거 백트래킹으로 짰다는..

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

문제

문제

출처

ICPC

RGB문제 어디서 틀렸을까요..?

lennie 7년 전 0

imgosari 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말