글 읽기 - 보이는 반례는 다 해본거 같습니다. 주석있으니 봐주시면 감사하겠습니다.

sotter1020 5년 전 0

부탁드립니다..

아무리 해도 뭐가 틀린지 모르겠습니다.

#include<iostream>
#include<vector>
#include<limits>

using namespace std;
#define min(y,x) ((y) > (x) ? (x) : (y));

const int INF = numeric_limits<int>::max();

vector<int> house[1001];
int cache[1001];
int n;

int cost(int morepre, int precolor, int home) {
	if (home == n) return 0;
	int& ret = cache[home];
	if (ret != INF) return ret;
	for (int color = 0; color < 3; color++) {
		if ((color == precolor || color == morepre) && home > 0 && home < n - 1) continue;
        // 첫번째 집과 마지막 집이 아닐 경우 n - 1과 n - 2번의 집 색은 continue한다.
        // 첫번째 집과 마지막 집은 이웃이 아니기 때문에 최솟값을 사용한다.
		ret = min(ret, cost(precolor, color, home + 1) + house[home][color]);
        // n-1번의 색과 현재 색의 정보를 다음집에 넘겨준다.
	}
	return ret;
}

void init() {
	for (int i = 0; i < 1001; ++i)
		cache[i] = INF;
}

int main() {
	init();
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; ++j) {
			int cost;
			cin >> cost;
			house[i].push_back(cost);
		}
	}
	cout << cost(-1, -1, 0) << endl;
	return 0;
}

jh05013 5년 전 0

질문을 올릴 때 "아래 공지사항을 먼저 읽고 글을 작성해 주세요." 라는 말이 나오는데 읽으셨나요? 그 글에 굵은 글씨로 "질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요." 라고 적혀 있습니다.

sotter1020 5년 전 0

아 죄송합니다.. 제가 문제를 오해하고 풀었기 때문이었네요 ㅠㅠ

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

문제

문제

출처

ICPC

보이는 반례는 다 해본거 같습니다. 주석있으니 봐주시면 감사하겠습니다.

sotter1020 5년 전 0

jh05013 5년 전 0

sotter1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말