글 읽기 - 이 코드에 대한 반례가 궁금합니다

daun20211 6년 전 0

다양한 케이스 별로 다 돌려봐도 오류를 찾지 못하겠네요

도와주세요.

#include<stdio.h>
int dy[1001][3], money[1001][3];
int min(int a, int b) {
	if (a > b)
		return b;
	return a;
}
int min3(int a, int b, int c) {
	if (a < b && a < c)
		return a;
	if (b < c && b < a)
		return b;
	return c;
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 3; j++) {
			scanf("%d", &money[i][j]);
			dy[i][j] = min(dy[i-1][(j + 1) % 3], dy[i-1][(j + 2) % 3]) + money[i][j];
		}
	printf("%d", min3(dy[n][0], dy[n][1], dy[n][2]));
}

waylight3 6년 전 0

dp식은 맞으니 아무래도 min3가 문제인 것 같습니다.

a == b < c인 경우, a와 b 모두 최소원소가 아니므로 c를 리턴하고 있어요. 원래대로라면 a나 b를(어차피 같지만) 리턴해야 합니다.

min3는 min(a, min(b, c))와 같이 짜시거나 <algorithm> 헤더에 있는 min({a, b, c})를 쓰시는게 안전합니다.

실제로 min 함수만 바꿔서 제출하니 맞았습니다를 받았습니다.

daun20211 6년 전 0

네 감사합니다.

min함수가 문제일줄이야...

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

문제

문제

출처

ICPC

이 코드에 대한 반례가 궁금합니다

daun20211 6년 전 0

waylight3 6년 전 0

daun20211 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말