글 읽기 - 반례 좀 찾아주세요,,

zpapl 6년 전 0

다 맞는 것 같습니다만,, 도대체 어디가 문제 입니까?ㅠㅠㅠㅠㅠ

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define colorNumber 3

int main() {
	//집의 수 N
	int N;
	//집의 가격
	vector<vector<int>> price;
	//DP 배열
	vector<vector<int>> dp;
	//선택한 컬러
	vector<vector<int>> selectedColor;
	//정답
	int Answer = 2147483647; //INT_MAX

	//변수 초기화
	cin >> N;
	price = vector<vector<int>>(N, vector<int>(colorNumber, 0));
	dp = vector<vector<int>>(N, vector<int>(colorNumber, 2147483647));
	selectedColor = vector<vector<int>>(N, vector<int>(colorNumber, -1));
	for (int i = 0; i < price.size(); i++) {
		for (int j = 0; j < colorNumber; j++) {
			cin >> price[i][j];
		}
	}

	//알고리즘
	//0은 별도로 초기화
	for (int i = 0; i < colorNumber; i++) {
			dp[0][i] = price[0][i];
			selectedColor[0][i] = i;
	}
	//colorNumber은 '3'이기 때문에 시간복잡도는 O(n-1)이라고 봄
	for (int i = 0; i < price.size() - 1; i++) {
		for (int j = 0; j < colorNumber; j++) {
			for (int k = 0; k < colorNumber; k++) {
				if (dp[i + 1][j] > price[i + 1][k] + dp[i][j] && k != selectedColor[i][j]) {
					dp[i + 1][j] = price[i + 1][k] + dp[i][j];
					selectedColor[i + 1][j] = k;
				}
			}
		}
	}

	//최소값 찾기 ((정답))
	for (int i = 0; i < colorNumber; i++) {
		if (Answer > dp[N - 1][i])
			Answer = dp[N - 1][i];
	}

	cout << Answer;
}

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

문제

문제

출처

ICPC

반례 좀 찾아주세요,,

zpapl 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말