[코드트리] 최대 이익 구하기2 (DP) - JAVA

 알고리즘 스터디 (백트래킹)

https://www.codetree.ai/training-field/search/problems/find-the-maximum-profit-2/description?page=1&pageSize=20&tags=Backtracking&order=tier

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

# 문제

# 예제

입력

6
1 4
1 4
1 6
3 10
1 3
1 8

 

출력

25

 

# 필요개념

 백트래킹에 들어있던 문제인데, 문제를 풀 당시에 dp밖에 떠오르지 않아 dp로 문제를 풀었다.

for문을 돌면서 dp배열에 여지까지의 최대 price를 담는 방식으로 풀었다.

 

나는 배열의 1 인덱스부터 넣었기 때문에 이를 감안해 if문에 조건을 넣어두었다. 이전까지의 최대 price와 현재 dp의 값을 비교해 최대값을 넣었다. 기간이 긴 경우에는 일이 끝난 날 (i가 1이고 t가 3 이라면 4에다) 해당 price를 반영해 넣었다.

 

# Code

import java.util.*;

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n + 1];

        List<Job> jobs = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            int t = Integer.parseInt(st.nextToken());

            int p = Integer.parseInt(st.nextToken());

            jobs.add(new Job(i + 1, t, p)); // 넣을 인덱스 지정

        }

        for (int i = 0; i < n; i++) {

       

            if (i < n) {

                dp[i + 1] = Math.max(dp[i + 1], dp[i]);

            }

            // 일이 끝나는 날짜 계산

            int endDay = i + jobs.get(i).time;

            if (endDay <= n) {

                dp[endDay] = Math.max(dp[endDay], dp[i] + jobs.get(i).pay);

            }

        }

        // 최대 이익 출력

        System.out.println(dp[n]);

    }

}

// 일(Job) 클래스 정의

class Job {

    int start; // 시작 날짜

    int time;  // 소요 기간

    int pay;   // 돈

    Job(int start, int time, int pay) {

        this.start = start;

        this.time = time;

        this.pay = pay;

    }

}

 

# 결과