카라멜마끼아또

개인 공부를 위한 공간입니다
상업적 용도로 활용되지 않습니다

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

T는 상담에 소요되는 시간

P 는 상담을 통해 받는 돈

조건

1. 상담은 동시에 하나

2. n+1 일부터는 이미 퇴사한 상태이기 때문에 상담 진행이 불가능

3. 상담이 끝난 후 돈을 받음 (다음날)

상향식으로 풀이

# 1일차

n=1

dp[1] = 0

1일차에는 어떤 상담도 완료되지 않았기 때문

1일차 이후 상담 가능한 날짜

int nextDay = 1 + t[1]

1일차 상담에는 3일이 소요되므로 nextDay = 1 + 3 = 4

dp[4] = max(dp[4], dp[1]+p[1])

dp[4] = (4일에 받을 수 있는 최대 금액) = (1일차 상담 3일치를 끝내고 받은 금액) = 10

# 2일차

n=2

dp[2] = 0

2일차 상담에는 5일 소요

nextDay = 2 + 5 = 7

dp[7] = max(dp[7], dp[2]+p[2])

dp[7] = 20

.....

# n일차

dp[n]=0

n일차 상담에는 t[n] 일 소요

nextDay = n + t[n]

dp[nextDay] = max(dp[nextDay], dp[n] + p[n])

** 주의

n번째 날의 상담 소요시간이 1일이라면, n+1 일에 금액을 받을 수 있으므로 dp 배열을 n+2 로 초기화

>> 1일 ~ n+1 일 까지

    public void solution15486() throws Exception{

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        int t[] = new int[n+2];
        int p[] = new int[n+2];
        int dp[] = new int[n+2];

        for(int i=1; i<=n; i++){
            String[] temp = reader.readLine().split(" ");
            t[i] = Integer.parseInt(temp[0]);
            p[i] = Integer.parseInt(temp[1]);
        }
        int max = -1;

        for(int i=1; i<=n+1; i++) {
            if(max < dp[i]){
                max = dp[i];
            }
            int nextDay = i+t[i];
            if(nextDay < n+2){
                dp[nextDay] = Math.max(dp[nextDay], max+p[i]);
            }
        }
        System.out.println(dp[n+1]);
    }