[백준] BOJ 14501 퇴사

문제 링크

문제 해석

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

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고,
비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

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

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

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다.
5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

문제 풀이

무식하게 풀 수 있는가?

무식하면 못푸는 문제 같은데 항상 무식하게 풀기부터 도전..
스택을 어찌어찌 잘 이용해서 max값 찾으면 될지도 모르겠다.
근데 그게 dp로 짜는거보다 쉬운지도 모르겠다..
그냥 dp로 풀기로 했음

다이나믹 프로그래밍으로 풀기!

💡다이나믹 프로그래밍은 메모이제이션이 핵심!

✨ 메모이제이션이란?
메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

1️⃣ 무엇을 메모하면 좋을까?

마감 기한을 고려하는게 핵심인 알고리즘이니까, 마감 날짜를 메모한다!
아래와 같이 기록!

memo[1] = 10
memo[2] = 30
memo[3] = 40
.
.
.
memo[8] = 90

memo[8]에는 8일까지 일했을 때의 최대 액수를 기록한다!

2️⃣ 마감 기한에 따른 최대 액수를 어떤 식으로 저장할 수 있을까?

아래 두가지 조건을 고려!

• 마감된 날짜가 같을 수는 없다.
• 하루도 안쉬고 일하는 것보다 띄엄띄엄 일하는 경우의 수익이 더 높을 수도 있다.

1. 마감된 날짜가 같을 수는 없다.

memo[pay[i][0]+i] = max(memo[pay[i][0]+i],pay[i][1]+memo[i]);

마감된 날짜가 같을 수는 없으니 해당 날짜의 페이는 아래 두가지 경우이다.

1) 해당 마감일에 원래 저장되어있던 pay
2) 오늘 pay, 오늘 마감인 과제 pay더한 값

더 큰 값을 저장해야 하므로, max를 써서 둘 중 더 큰 값을 출력

2. 하루도 안쉬고 일하는 것보다 띄엄띄엄 일하는 경우의 수익이 더 높을 수 있다.

memo[i] = max(memo[i], max);
max = max(max, memo[i]);

i일 까지 일했을 때 최대값은 다음 두가지 경우 중 하나이다.

1) i일 까지 꽉 채워서 일한 경우
2) i일에 일하지 않은 경우

따라서 memo[i]나 이전 저장된 값인 max 중 더 큰 값을 memo한다.

문제 풀이 코드

package DP;

import java.util.Scanner;

import static java.lang.Math.max;

public class BOJ14501 {
    static int[][] pay;
    static int day;
    static int[] memo;
    static int max = 0;
    public static void main(String[] args) {
        //입력 배열로 정돈해서 받기
        Scanner s = new Scanner(System.in);
        day = s.nextInt();
        pay = new int[day + 10][2];
        for (int i = 1; i < day+1; i++) {
            pay[i][0] = s.nextInt();
            pay[i][1] = s.nextInt();
        }
        //메모 선언
        memo = new int[day + 10];
        //DP돌림
        DP(pay);
    }
    static void DP(int[][] pay) {
        for (int i = 1; i <=day+1; i++) {
            //이전까지의 최대 수입을 비교해서 최대 수입을 현재에도 저장해준다.
            //이전에 최대수입이 났을 수 있으므로
            //ex) 3,7,(5 예상) 이라고 하면 5의 값은 7로 바꿔주는게 최대수입을 얻는데 맞다.
            memo[i] = max(memo[i], max);
            //이전에 저장된 최대수익 vs 이번 움직임으로 생긴 최대 수익
            memo[pay[i][0]+i] = max(memo[pay[i][0]+i],pay[i][1]+memo[i]);
            //출력될 최대 수입
            max = max(max, memo[i]);
        }
        System.out.println(max);
    }

}