퇴사 2(15486번)

• 티어 : Gold 5
• 정답여부 : 오답
• 알고리즘 유형 : 다이나믹 프로그래밍
• 시간 제한 : 2초

💡문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

💡입력

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

💡출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

💡예제 입력 1

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

💡예제 출력 1

45

💡예제 입력 2

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

💡예제 출력 2

55

💡예제 입력 3

10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6

💡예제 출력 3

20

💡예제 입력 4

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

💡예제 출력 4

90

💡문제요약

• 기간 내에 상담을 하여 최대 수익을 출력하면 되는 문제

💡알고리즘 설계

• N : 상담일
• time, pay : 각 날짜에 해당하는 상담시간과 상담 가격

1. 각 날짜에 상담 시간과 상담 가격을 입력받고 time과 pay 에 넣어줌
2. 현 상담시 종료일보다 작아야함(N 보다 큰 경우 상담 불가 그 이후 퇴사)
3. 현재 상담을 진행할 경우의 최대 수익과 이전 날짜의 최대 수익을 비교하여 더 큰 값을  dp 배열에 저장
4. 이전 날의 상담 누적값 + 오늘자 상담의 금액을 오늘 진행한 상담이 끝나는 요일에 저장(비교 후 저장)
5. 마지막 날짜 N의 최대 수익을 출력

💡작성코드

• Java

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 schedule[][] = new int[N][2];
        int[] dp = new int[N + 1]; // 배열 크기를 N+1로 설정    
        for (int i = 0; i < N; i++) { // 해당 날짜 상담의 소요일과 금액 저장
            String[] tp = br.readLine().split(" ");
            schedule[i][0] = Integer.parseInt(tp[0]); // 상담날짜
            schedule[i][1] = Integer.parseInt(tp[1]); // 상담 가격
        }
        for (int i = 0; i < N; i++) { // 반복문 범위를 i < N으로 수정
            int time = schedule[i][0];
            int pay = schedule[i][1];
            if (i + time - 1 < N) { // i + time - 1이 N을 초과하지 않는지 확인
                // 생각이...정말 안 나... 비교 어찌하노!
                dp[i + time] = Math.max(dp[i + time], dp[i] + pay); // dp[i + time - 1]에 저장
            }         
            dp[i + 1] = Math.max(dp[i + 1], dp[i]); // 이전 날과 오늘 중 더 큰 금액 저장
        }    
        System.out.println(dp[N]); // 마지막 날짜 N의 최대 수익 출력
    }
}

💡시간복잡도

O(N)

💡틀린 이유 or 수정할 부분

값을 설정하고 나서 비교를 해야하는 부분에서 좀 많이 막힌거 같았다. 값을 어떻게 비교해야할지 생각이 안 나서 구글링을 했다. 생각해보니 최대값이면 바로 max 함수를 써서 구현을 하면 되는데 그 간단한걸 생각못했다.
그리고 굳이 배열을 설정하지 않아도 구현이 가능한 문제였다. 배열로 설정을 하지 않으니 좀 더 시간이 단축된거 같다.

💡틀린 부분 수정 or 다른풀이

• Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
    private int N;
    private int[] dp;
    private int T, P;
    private int max;
    private int res;
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];
        max = 0;
        res = 0;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            T = Integer.parseInt(st.nextToken());
            P = Integer.parseInt(st.nextToken());
            max = Math.max(max, dp[i - 1]);
            if (i + T - 1 <= N) {
                dp[i + T - 1] = Math.max(dp[i + T - 1], max + P);
                res = Math.max(res, dp[i + T - 1]);
            }
        }
        System.out.println(res);
    }
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

💡느낀점 or 기억할 정보

점화식을 제대로 갈피를 못 잡은 문제였다. 잠을 요즘 못 자서 그런지 집중력이 조금 떯어지는거 같다. 한번 다시 맨 정신에 다시 풀어봐야겠다.