[DP] 메이플스토리(백준 20925번,자바)

 

문제

메이플스토리에는 여러 가지 사냥터가 있다. 각 사냥터는 입장에 필요한 최소 레벨, 지형, 몬스터 레벨, 몬스터 수, 버닝 등등 다양한 특징을 가진다. 상원이는 경험치가 가장 중요하기 때문에 사냥터의 특징을 입장에 필요한 최소 경험치와  1분마다 얻는 경험치로 간략화 했다. 사냥을 시작하고 매 분마다 지금 있는 사냥터에서 계속 사냥할지 다른 사냥터로 갈지 결정한다. 코디 아이템에 돈을 다 써 텔레포트를 할 수 없는 상원이는 사냥터 사이를 직접 걸어서 이동한다. 사냥터 사이를 이동하는 동안 사냥을 할 수 없기 때문에 경험치를 얻을 수 없다.

처음에 캐릭터의 경험치는0이기 때문에 입장에 필요한 최소 경험치가 0$0$인 사냥터 중 하나를 골라 사냥을 시작한다. 상원이가 방학 동안 얻을 수 있는 경험치의 최댓값을 알려주자.

입력

첫째 줄 사냥터 수 N(1≤N≤200) 과 방학 기간을 분 단위로 나타낸 T(1≤T≤100)가 주어진다.

다음 N개의 줄에는 i번째 사냥터의 특징인 입장에 필요한 최소 경험치 ci와 1분마다 얻는 경험치 ei가 주어진다. (0≤ci, ei≤1000000)

다음 N개의 줄에는 각 사냥터 사이를 이동하는 데 걸리는 시간이 주어진다. i번째 줄의 j번째 수는 i번 사냥터에서j번 사냥터로 이동하여 입장하는 데까지 걸리는 시간을 분 단위로 나타낸 값 ti, tj이다. (1≤ti, tj≤1000)

단, 입장에 필요한 최소 경험치  0인 사냥터는 반드시 하나 이상 존재한다.

출력

상원이가 방학 동안 얻을 수 있는 경험치의 최댓값을 출력한다.

 

구현

1. DP 이용, dp[사냥터][시간]=경험치
2. (1. 같은 사냥터를 계속 이동하는 경우)=> 보유한 경험치가 해당 사냥터의 입장에 필요한 최소 경험치인지 확인

if(dp[j][i-1]>=huntingGround[j][0]) dp[j][i]=dp[j][i-1]+huntingGround[j][1];

     

    (2. 다른 사냥터로 이동하는 경우)=> 해당 사냥터로 이동 전의 경험치가 해당 사냥터의 입장에 필요한 최소 경험치인지 확인

if(i-time[k][j]>0 && dp[k][i-time[k][j]]>=huntingGround[j][0]) {
				dp[j][i]=Math.max(dp[j][i],dp[k][i-time[k][j]]);
			}

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N, T;
	static int[][] dp;
	static int[][] huntingGround;
	static int[][] time;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		T=Integer.parseInt(st.nextToken());
		
		dp=new int[N+1][T+1];
		huntingGround=new int[N][2];
		time=new int[N][N];
	
	
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			huntingGround[i][0]=Integer.parseInt(st.nextToken());
			huntingGround[i][1]=Integer.parseInt(st.nextToken());
		}
		
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				time[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		
		for(int i=0;i<N;i++) {
			if(huntingGround[i][0]==0) dp[i][1]=huntingGround[i][1];
		}
	
		
		for(int i=2;i<=T;i++) { //시간
			for(int j=0;j<N;j++) { //사냥터
				if(dp[j][i-1]>=huntingGround[j][0]) dp[j][i]=dp[j][i-1]+huntingGround[j][1];
				for(int k=0;k<N;k++) {	
					if(j==k) continue;
					if(i-time[k][j]>0 && dp[k][i-time[k][j]]>=huntingGround[j][0]) {
							dp[j][i]=Math.max(dp[j][i],dp[k][i-time[k][j]]);
						}
					}
				}
		}
		
		int answer=0;
		for(int i=0;i<N;i++) {
			if(answer < dp[i][T]) answer=dp[i][T];
		}
		System.out.println(answer);

	}

}