글 읽기 - 카드 게임 질문입니다~

sksdong1 8년 전 0

dp로 각 번호에 대해 카드들이 빠질 조건, 점수를 얻을 조건에 맞춰서 아래와 같이 짯는데 어디가 잘못된걸까요ㅜㅜ

import java.util.Scanner;

class Main{
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int num=1,N,max=0;
		N=sc.nextInt();
		int left[] = new int[N+1];
		int dp[][] = new int[N+1][N+1];

		for(int i=1;i<=N;i++){
			left[i]=sc.nextInt();
		}
		for(int i=1;i<=N;i++){
			dp[i][0]=sc.nextInt(); //오른쪽 더미
		}
		for(int i=1;i<=N;i++){ //i는 right에서 각 숫자 2,4,1을 뜻함
			boolean flag=false;
			for(int j=num;j<=N;j++){ //num은 left 더미의 시작 위치.
				if(flag) 
					dp[i][j]=dp[i][j-1];
				else if(dp[i][0]<left[j]){ // right<left이면  right는 빼고 점수 증가, -> 왼쪽 더미 변화 x(num 유지)
					num=j;
					dp[i][j]=dp[i-1][j]+dp[i][0];
					flag=true; 
				}
				else{
					dp[i][j]=dp[i-1][j];
				}
			}
			if(!flag) num++; //오른쪽 더미에서 하나도 점수를 얻은 것이 없을 시 오른쪽 더미, 왼쪽 더미 모두 카드 제거.
		}
		for(int i=1;i<=N;i++){
			if(max<dp[i][N]) max=dp[i][N];
		}
		System.out.println(max);
	}
}

yukariko 8년 전 0

왼쪽 카드만 버리거나, 오른쪽 카드만 버리거나, 둘 다 버리거나의 3택이 가능한데,

위 소스는 2가지만을 고려한 것 같습니다.

sksdong1 8년 전 0

23줄에 num=j를 넣고 19줄에서 num부터 탐색 시작하도록 해서 왼쪽만 버리는 용도(num개 만큼) 의도했고

17줄 for문 한바퀴 돌때마다 오른쪽을 버리도록 의도했고, 이 과정에서 점수를 먹는다면 오른쪽만 하나 증가되고, 점수를 못먹는다면

31줄에서 num++ 해서 왼쪽 오른쪽 둘다 버리도록 의도했는데

3개 다 고려한거 아닌가용??

yukariko 8년 전 0

음.. 이 소스는 동적계획법으로 구현이 된것이 아닌것 같습니다.

지금의 소스는 이전 dp 값을 활용하여 크기 비교하는 과정이 없고,

dp[i][j]에 값을 할당하는 부분만이 존재합니다.

그렇다면 이 소스는 동적계획법이 아닌, 그리디 해법입니다.

오른쪽 카드만 택할 수 있는 상황엔 오른쪽 카드만 택하는게 맞지만,

그 외의 상황에선 왼쪽 카드만 택하거나, 양쪽 카드를 택했을 때의 결과 중의 최대를 골라야 합니다.

sksdong1 8년 전 0

아 그러네요 감사합니다!!

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

문제

문제

출처

ICPC

카드 게임 질문입니다~

sksdong1 8년 전 0

yukariko 8년 전 0

sksdong1 8년 전 0

yukariko 8년 전 0

sksdong1 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말