백준 알고리즘 | 14585 | 사수빈탕ㅣJava

문제

수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 N개의 사탕바구니가 있고, 각 사탕 바구니에는 M개의 사탕이 있다. 각 사탕 바구니는 (x1, y1), (x2, y2), …, (xn, yn)에 있고, 수빈이는 (0, 0)에 있다.
오늘은 날씨가 덥다. 따라서 시간이 1만큼 지날 때마다 사탕이 남아 있는 모든 사탕바구니에서 사탕은 한 개씩 녹아서 없어진다. 수빈이는 매우 배가 고프기 때문에, 사탕바구니에 있는 사탕을 순식간에 모두 먹을 수 있다. 수빈이가 1만큼 움직일 때, 시간은 1만큼 지나간다. 수빈이는 위쪽 (y-좌표가 늘어나는 방향) 또는 오른쪽 (x-좌표가 늘어나는 방향)으로만 움직일 수 있다.
수빈이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다.
둘째 줄부터 N개의 줄에 사탕 바구니의 위치 xi, yi가 주어진다. (0 ≤ N ≤ 300, 1 ≤ M ≤ 1,000,000, 0 ≤ xi, yi ≤ 300)
사탕 바구니의 위치는 중복되지 않으며, (0, 0)에는 사탕이 없다.

출력

수빈이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제

입력	출력
3 15 1 1 3 1 1 6	24

풀이

DP로 풀어보자

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class BOJ14585
{
	static int n;	// 사탕바구니의 수
	static int m;	// 사탕바구니 속 사탕의 수
	static int [][] map ;	// 사탕바구니 위치를 저장할 2차월 배열이며 
								// 0 ≤ xi, yi ≤ 300 이므로 크기는 301 x 301
	static int [][] Record;
	static int limit;	// 사탕바구니를 모두 지나면 끝내기
	static int xyMax;	// 가장 멀리있는 바구니의 x,y 값 중 큰 값
	
	static int ans;
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		xyMax=0;
		map=new int[301][301];
		Record=new int[301][301];
		
		for(int i=0;i<n;i++)
		{
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[x][y]=m;
			
			// 평면은 301 x 301 이지만 x,y가 존재하는 위치까지만 확인하기 위해 x,y 값 중 최대값 확인 
			if(x>=xyMax||y>=xyMax)
			{
				xyMax=Math.max(x,y);
			}
		}
		
		ans = 0; 
		limit=0;
		
		//(0,0) 위치부터 최댓값 확인
		for(int i=0;i<=xyMax;i++)
		{
			for(int j=0;j<=xyMax;j++)
			{
				dp(i,j);
			}
		}
		
		bw.write(ans+"\n");
		br.close();
		bw.flush();
		bw.close();
	}
	
	static void dp(int i, int j)
	{
		// 사탕바구니를 모두 확인하였으면 종료
		if(limit==n) return;
		
		// 사탕바구니가 있는 위치라면 limit 증가
		if(map[i][j]==300) limit++;
		
		int right=0;	// (i,j-1) 위치로부터 오른쪽(->)에 (i,j)가 위치, (i,j-1)의 최대값 변수
		int up=0;		// (i+1,j) 위치로부터 위쪽(^)에 (i,j)가 위치, (i+1,j)의 최대값 변수
		
		//(i,j-1) 위치가 유효한 경우
		if(i>=0&&i<301&&j-1>=0&&j-1<301)
		{
			right=Record[i][j-1];
		}
		
		//(i-1,j) 위치가 유효한 경우
		if(i-1>=0&&i-1<301&&j>=0&&j<301)
		{
			up=Record[i-1][j];
		}
		
		// (i,j-1)과 (i-1,j) 중 큰 값 가져오기
		Record[i][j]=Math.max(right,up);
		
		// (i,j) 위치에 사탕이 있고 가는 동안(i+j) 녹지 않은 사탕이 있다면, 추가
		if(map[i][j]-(i+j)>=0) Record[i][j]+=map[i][j]-i-j;
		
		//최대값 확인
		ans=Math.max(ans, Record[i][j]);
		
	}
}

기타

다른 코드들을 참고해보니 0,0->x,y로 가는 방향보다, x,y에서 0,0로 오는 방향으로 계산하면 더 빠르게 계산할 수 있는 것 같다.