글 읽기 - 10982 질문입니다.

chatterboy 8년 전 0

두 오븐의 시간차가 200을 넘으면 최적이 아니다라고 가정하고 점화식을 세웠습니다.

T[pos][diff][flag] = [0...pos]까지 고려하고 두 오븐의 시간 차가 diff일 때, 최적값 (flag는 0일 때 오븐 A의 시간 > 오븐 B의 시간)

접근이 잘못된 것인가요? ㅠㅠ

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

#define a first
#define b second

int N;
vector<pair<int,int>> cookie;
int cache[1000][200][2];

int solve(int pos, int diff, int flag) {
	if (diff >= 200) return inf;
	if (pos == N) return 0;
	int &ret = cache[pos][diff][flag];
	if (ret != -1) return ret;
	ret = inf;
	if (flag) {	// B가 더 클 때
		ret = min(ret, solve(pos + 1, diff + cookie[pos].b, flag) + cookie[pos].b); // B에서 구울 때
		// A에서 구울 때
		if (diff >= cookie[pos].a)
			ret = min(ret, solve(pos + 1, diff - cookie[pos].a, flag));
		else
			ret = min(ret, solve(pos + 1, cookie[pos].a - diff, 1 - flag) + cookie[pos].a - diff);
	} else { // A가 클 때
		ret = min(ret, solve(pos + 1, diff + cookie[pos].a, flag) + cookie[pos].a);
		if (diff >= cookie[pos].b)
			ret = min(ret, solve(pos + 1, diff - cookie[pos].b, flag));
		else
			ret = min(ret, solve(pos + 1, cookie[pos].b - diff, 1 - flag) + cookie[pos].b - diff);
	}
	return ret;
}

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		scanf("%d", &N);
		cookie = vector<pair<int,int>>(N);
		for (int i = 0; i < N; i++)
			scanf("%d%d", &cookie[i].a, &cookie[i].b);
		memset(cache, -1, sizeof(cache));
		printf("%d\n", min(solve(0, 0, 0), solve(0, 0, 1)));
	}
	return 0;
}

alohajihwan 7년 전 0

저도 이런 방식으로 접근했는데 혹시 예외상황 알수 있을 까요?

alohajihwan 7년 전 1

아 해결되었습니다. 감사합니다!

hongjg3229 3년 전 0

저도 이렇게 생각하고 풀어서 엄청 틀렸는데, 저 가정이 잘못됐던거였습니다.. ㅜㅜ

처음 생각에서 탈피하기가 힘들었습니다.

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

문제

문제

출처

ICPC

10982 질문입니다.

chatterboy 8년 전 0

alohajihwan 7년 전 0

alohajihwan 7년 전 1

hongjg3229 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말