퇴사

www.acmicpc.net/problem/14501

14501번: 퇴사

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;

int n;

int dp[17];


int main() {
	

	cin >> n;

	memset(dp, 0, sizeof(dp));
	
	vector<int>t(n+2); //days
	vector<int>p(n+2); //profit
	
	
	for (int i = 1; i <= n; i++) {
		
			
		cin >> t[i];
		cin >> p[i];

	}

	int ans = 0;

	for (int i = 1; i <= n + 1; i++) {
		for (int j = 1; j < i; j++) {
		
		
			dp[i] = max(dp[i], dp[j]); // j를 거치지 않고 i에 도착했을때
		
			if (j + t[j] == i) {
				dp[i] = max(dp[i], dp[j] + p[j]); //j를 거쳐서 i에 도착했을 때
				
			}
		}
		ans = max(ans, dp[i]);
	}


	cout<<ans<<endl;

	
	
	}

	

<JAVA>

package Samsung;

import java.io.*;
import java.util.*;
public class 퇴사 {
	
	static int n;
	static int[] t;
	static int[] p;
	static int[] d;
	
	public static void main(String[]args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		n = Integer.parseInt(br.readLine());
		t = new int[n+1];
		p = new int[n+1];
		d= new int[n+2];
	
		StringTokenizer st;
		for(int i=1; i<=n; i++) {
			
			st = new StringTokenizer(br.readLine());
			
			t[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
			
		}
		
		for(int i=1; i<=n; i++) {
			
			d[i] = Math.max(d[i], d[i-1]); //이전에 끝나서 받은 금액과 비교했을때 이전게 더 트면 이전 금액으로 갱신
			int j = t[i]+i;
			if(j>n+1)continue; 
			d[j] = Math.max(d[j], d[i]+p[i]); //현재 시작해서 끝나는 날에 받게 될 금액을 비교해서 갱신한다
			
			
		}
		
		int max =0;
		for(int i=1; i<=n+1; i++) {
			max = Math.max(max, d[i]);
		}
		System.out.println(max);
	}
	
	

}