글 읽기 - 맞았는데 오답인 경우는 절대 없는거죠?

qazxsw100415 5년 전 1

한국정보올림피아드 사이트에서 체점 데이터를 다운로드 받아 모든 데이터를 하나하나 대입해본 결과 모두 정답과 일치하던데, 제출해보니 "틀렸습니다" 가 나오더군요.

도대체 뭐가 잘못된 걸까요..

#include <iostream>
#include <algorithm>

using namespace std;

#define INF 2000000000

int n, m;
bool* check;
int** dp; //dp[c][d] d번째 날에 쿠폰 c개를 남기고 지불 가능한 최솟값

int oneDay(int coupon, int day) {
	return dp[coupon][day - 1] + 10;
}

int threeDay(int coupon, int day) {
	if (coupon < 1 || day < 3) return INF;
	return dp[coupon - 1][day - 3] + 25;
}

int fiveDay(int coupon, int day) {
	if (coupon < 2 || day < 5) return INF;
	return dp[coupon - 2][day - 5] + 37;
}

int useCoupon(int coupon, int day) {
	if (coupon > n / 5 * 2 - 1) return INF;
	return dp[coupon + 3][day - 1];
}

int solve() {
	for (int i = 0; i < n + 1; i++) {
		for (int j = 0; j < n / 5 * 2 + 3; j++) {
			int minCost = INF;
			bool check_ = true;

			if (i == 0 && j == 0) {
				dp[j][i] = 0;
				check_ = false;
			}
			if (i == 0) check_ = false;
			if (!check[i]) {
				dp[j][i] = dp[j][i - 1];
				check_ = false;
			}

			if (check_) minCost = oneDay(j, i);
			if (check_ && threeDay(j, i) < minCost) minCost = threeDay(j, i);
			if (check_ && fiveDay(j, i) < minCost) minCost = fiveDay(j, i);
			if (check_ && useCoupon(j, i) < minCost) minCost = useCoupon(j, i);
			if (check_) dp[j][i] = minCost;
		}
	}

	int minCost = INF;
	for (int i = 0; i < n / 5 * 2 + 3; i++) minCost = min(minCost, dp[i][n]);
	return minCost;
}

int main() {
	cin >> n >> m;
	dp = new int*[n / 5 * 2 + 3];
	for (int i = 0; i < n / 5 * 2 + 3; i++) {
		dp[i] = new int[n + 1];
		fill(dp[i], dp[i] + n + 1, INF);
	}
	check = new bool[n + 1];
	fill(check, check + n + 1, true);

	for (int i = 0; i < m; i++) {
		int temp;
		cin >> temp;
		check[temp] = false;
	}

	cout << solve() * 1000 << endl;

	for (int i = 0; i < n / 5 * 2 + 3; i++) delete[] dp[i];
	delete[] dp;
	delete[] check;
    
    return 0;
}

03ysh03 5년 전 0

반환값이 없어서 그런걸수도.

qazxsw100415 5년 전 0

아.. 그럴 듯 했는데 return 0; 써도 그대로네요.

djm03178 5년 전 4

이 케이스의 정답은 62000입니다. https://ideone.com/X6X30e

1 2 3 4 5일을 5일권으로 사서 쿠폰 2장을 얻고, 7, 8, 9일을 3일권으로 사서 쿠폰 1장을 얻고, 10일째는 쿠폰 3장을 소모하면 됩니다.

qazxsw100415 5년 전 0

헉.. 감사합니다. 기간이 끝나는 날과 리조트에 가지 못하는 날이 겹칠 수 있다는 사실을 잊고 있었네요.

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

문제

문제

출처

ICPC

맞았는데 오답인 경우는 절대 없는거죠?

qazxsw100415 5년 전 1

03ysh03 5년 전 0

qazxsw100415 5년 전 0

djm03178 5년 전 4

qazxsw100415 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말