글 읽기 - 어느정도 채점하다 틀렸습니다 뜨네요.

lakshimi 4년 전 0

dp를 이용해서 프로그램을 작성했습니다.

기본적인 알고리즘은 오른쪽 카드를 버릴 수 없는 경우는 -1로 처리를 했습니다.

dp[x][y] 에서 x는 왼쪽 덱에 버린 카드수, y는 오른쪽 덱에서 버린 카드수입니다. dp[n][n] 상태는 모든 덱에 있는 카드를 버린 경우입니다.

예제를 여러가지 테스트해보았는데, 반례를 찾기 힘드네요.

일단 테스트를 위해서 dp 내용을 찍는 것까지 추가했습니다.

#include <stdio.h>

int main()
{
	int n, a[2000], b[2000];
	static int dp[2001][2001];
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", a + i);
	for(int i = 0; i < n; i++) scanf("%d", b + i);
	for(int i = 1; i <= n; i++)
	{
		dp[i][0] = 0;
		dp[0][i] = (dp[0][i - 1] != -1 && a[0] > b[i-1]) ? dp[0][i-1] + b[i-1] : -1;
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			int max = dp[i - 1][j - 1];
			if(max < dp[i-1][j]) max = dp[i-1][j];
			if(dp[i][j - 1] != -1 && i < n && a[i] > b[j - 1] && max < dp[i][j - 1] + b[j - 1]) max = dp[i][j - 1] + b[j - 1];
			dp[i][j] = max;
		}
	}
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j <= n; j++) printf("%d ", dp[i][j]);
		putchar('\n');
	}
	printf("%d\n", dp[n][n]);
	return 0;
}

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

문제

문제

출처

ICPC

어느정도 채점하다 틀렸습니다 뜨네요.

lakshimi 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말