글 읽기 - 반례좀 찾아주세요ㅠㅠ 게시판 다뒤졌는뎅

zizon233 5년 전 0

반례를 못찾겠어여..... 갓 센세여러분 존경합니다.

#include <iostream>
#include <algorithm>
using namespace std;
int select(int a, int b, int x, int y, int z) {
	if (a == b) {
		if (a == 1) {
			return min(y, z);
		}
		else if (a == 2) return min(x, z);
		else return min(x, y);
	}
	else {
		if (a == 1)
			if (b == 2) return z;
			else return y;
		else if (a == 2)
			if (b == 3) return x;
			else return z;
		else
			if (b == 1) return y;
			else return x;
	}
}

int select2(int a, int x, int y, int z) {
	if (a == 1) {
		return min(y, z);
	}
	else if (a == 2) return min(x, z);
	else return min(x, y);
}
int main()
{
	int N, R[1000], G[1000], B[1000], dp[1000] = { 0 }, low[1000] = { 0 };
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> R[i] >> G[i] >> B[i];
		if (R[i] > G[i]) {
			if (G[i] > B[i]) low[i] = 3;
			else low[i] = 2;
		}
		else {
			if (R[i] > B[i]) low[i] = 3;
			else low[i] = 1;
		}
	}
	dp[0] = min(R[0], min(G[0], B[0]));
	dp[1] = min(dp[0] + select2(low[0], R[1], G[1], B[1]),min(R[1],min(G[1],B[1]))+select2(low[1],R[0],G[0],B[0]));
	for (int i = 2; i < N; i++) {
		dp[i] += min(dp[i - 2] + select(low[i - 2], low[i],R[i-1],G[i-1],B[i-1])+min(R[i],min(G[i],B[i])), dp[i - 1] + select2(low[i - 1],R[i],G[i],B[i]));
	}
	cout << dp[N - 1];
	return 0;
}