백준 14501 퇴사

문제

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

코드

python

n = int(input())
lis = []
for i in range(n):
    t, p = map(int, input().split())
    lis.append((t, p))

dp = [0]*(n+1)

for i in range(n-1, -1, -1):
    t, p = lis[i]
    if i+t > n:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], p+dp[i+t])
print(dp[0])

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static int n,m;
    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer((bf.readLine()));

        int n=Integer.parseInt(st.nextToken());
        int[][] tp=new int[2][n];
        int[] dp=new int[n+1];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(bf.readLine());
            tp[0][i] = Integer.parseInt(st.nextToken());
            tp[1][i] = Integer.parseInt(st.nextToken());
        }
        for(int i=n-1;i>=0;i--){
            int t=tp[0][i];
            int p=tp[1][i];
            if(i+t>n) dp[i]=dp[i+1];
            else dp[i]=Math.max(dp[i+1],p+dp[i+t]);
        }
        System.out.println(dp[0]);
    }
}

cpp

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <math.h>
#include <numeric>


using namespace std;


int main() {
	int n;
	cin >> n;
	vector<int> dp(n+1, 0);
	vector<vector<int>> input(n,vector<int>(2));
	for (int i = 0; i < n; i++) {
		cin >> input[i][0];
		cin >> input[i][1];
	}
	if (input[n - 1][0] == 1)dp[n - 1] = input[n - 1][1];
	for (int i = n-2; i >=0; i--) {

		if (input[i][0] + i > n) {
			dp[i] = dp[i + 1];
			continue;
		}

		dp[i] = max(dp[input[i][0] + i] + input[i][1],dp[i+1]);
		
	}
	cout << dp[0];
}

풀이

퇴사날부터 역으로 얻을 수 있는 최대의 수익을 dp 테이블에 저장했습니다