[JAVA] 백준_14501_퇴사

문제링크

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

import javax.swing.plaf.synth.SynthSpinnerUI;

public class Main {

	static int N;
	static int result = 0;
	static int sum = 0;
	static int time[],price[],date[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		
		time = new int[N+1];
		price = new int[N+1];
		date = new int[N+1];
		
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			time[i] = Integer.parseInt(st.nextToken());
			price[i] = Integer.parseInt(st.nextToken());
			
			date[i] = price[i];
		}
		
		//date[i] 에는 현재 날짜까지의 최대 금액? 저장하기
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=i;j++) {
				if(i-j >=time[j])
					date[i] = Math.max(date[i], price[i]+date[j]);
			}
		}
		
		for(int i=1;i<=N;i++) {
			if(i+time[i]<=N+1) {
				result = (result<date[i])?date[i]:result;
			}
		}
		
		System.out.println(result);
	}
	

}

 

 

DFS와 BFS로 풀어볼려고 했다가 시간 엄청 많이 잡아먹었다.

놓쳤던 부분은 맨처음 접근할때는 첫번째 날 + 걸리는 날짜 만큼 가면서 구했는데

첫번째 날에서 일이 3일 걸리더라도 4번째 날에 시작 안하고 다음 5번째 날부터 시작하는 것이 최대 이익일 수 있는 부분을 고려를 안했다.

 

따라서 문제를 풀 때 현재 날짜까지 얻을 수 있는 최대 이익을 구해야했다.

따라서 date[] 배열을 만들어 준 뒤 이 배열에는 현재 날짜까지(date[1] 은 첫번째 날 까지 date[2]는 두번째 날,,)의 최대 이익을 구해 주었다.

 

이 포문이 현재 날짜까지의 최대 이익을 구해주는 부분이다.

일단 i가 현재 날짜이고 j는 그 첫째 날 부터 i번째 날짜까지의 포문을 돌면서 구한다.

i-j>=time[j]를 통해 현재 날짜가 갈 수 있는 날짜?면 그러니까 j번째 날짜에 일을해서 현재 날짜보다 더 오래 걸리면 안되니까 이런 경우에는 date[i]에 저장되어 있는 이득과 현재날짜의 이득 price[i]와 이전 날짜의 최대 이득 data[j] 를 더한 값을 비교하여 더 큰 값을 현재 날짜에 얻을 수 있는 최대이득 배열에 넣어준다.