👩‍💻 BOJ_14501_퇴사

💬 퇴사의 염원을 담아, 문제를 풀었지만 DP는 풀어도 풀어도 어려운 것을 느꼈습니다. 하루 내내 잡고 있어도 안 되어서 해설을 보고 이해하는 식으로 해결했습니다. 다음에 실력을 더 쌓아 스스로 풀어보고 싶습니다.

📄 문제

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

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

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

💡 풀이 방법

• 이러한 유형의 DP 문제는 뒤에서부터 확인하는 것이 편하다고 어디선가 들었습니다. N부터 1까지 뒤에서 앞으로 최적 비용(제일 큰 값) 을 누적해 저장해줍니다. 그렇게 되면 배열의 첫번째 순서에 최대값이 저장됩니다.

• 우선, 값을 저장하는 배열을 3개 만듭니다.
  ✔️ 1일-N일까지로 배열 순서를 맞추고 싶어 int xxx = new int[N+1]; 로 선언합니다.
  1) 소요되는 시간 : time[]
  2) 얻을 수 있는 비용 : money[]
  3) 최적 비용을 메모 : memo[]
  
  ✔️ 메모의 경우는 퇴사 일이 N+1임을 고려해 배열 크기를 +1 해줍니다.
  ✔️ int memo[] = new int[N+2]; 로 처음에 초기화를 하니 모든 값은 0입니다.

• time[N]은 N일에 시작 시 소요되는 시간입니다. 퇴사 전까지 열심히 일을 해야하기 때문에 퇴사 전에 끝내는 경우 / 퇴사 전까지 끝내지 못하는 경우로 나눌 수 있습니다.

• money[N]은 말 그대로 N일에 시작한 일을 끝낼 경우 받을 수 있는 보수입니다.
  
  

  ---

1️⃣ 퇴사 전까지 못 끝내는 경우

🤔 예를 들어 퇴사 예정 일은 8일(N+1)입니다. 7일(N)에 시작할 때, 2일이 걸린다고 하면 퇴사 날짜인 8일 보다 후인 9일에 끝나니 작업을 할 수 없습니다.

• memo[N+1]의 값인 0을 memo[N]에 저장해줍니다.
• for문 안에서 돌아가는 식으로 표현 시, memo[i] = memo[i+1] 가 되겠습니다.
  
  

2️⃣ 퇴사 전에 끝내는 경우

🤔 예를 들어 퇴사 예정 일은 8일(N+1)입니다. 5일(N-3)에 시작할 때, 2일이 걸린다고 하면 퇴사 날짜인 8일 보다 전인 7일에 끝나니 작업을 할 수 있습니다.

뒤에서 누적해서 보수를 저장해왔기 때문에 memo[6]에 저장된 값은 6, 7일에 시작해서 얻은 보수의 값의 합입니다. 둘 다 퇴사 전에 끝내지 못했다고 가정하면 memo[i+1]은 0입니다.

6일에 시작해 얻을 수 있는 보수는 money[5]에 memo[7]을 더한 값입니다.
5일에 시작하면 5, 6일을 소요해 7일에 시작이 가능하기 때문입니다. (그러나 7일에 시작하면 퇴사 전에 끝내지 못하니 memo[7]은 0입니다.)

• 누적된 값(memo[i+1])과 현재 시작했을 때 얻을 수 있는 보수를 비교해 큰 값을 memo[i]에 저장합니다.
• for문 안에서 돌아가는 식으로 표현 시, memo[i] = Math.max(memo[i+1], memo[i+time[i]]+money[i]); 가 되겠습니다.
  
  

😀 최종적으로 memo[1]에 저장된 값이 최대로 벌 수 있는 보수가 됩니다.

🔥 코드

import java.util.Scanner;

public class 퇴사 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		// 퇴사까지 남은 일수 : 퇴사는 N+1
		int N = sc.nextInt();
		
		// 걸리는 시간, 보수, 누적 보수 메모
		int time[] = new int[N+1];
		int money[] = new int[N+1];
		int memo[] = new int[N+2]; 
		
		for(int i = 1; i < N+1; i++) {
			time[i] = sc.nextInt();
			money[i] = sc.nextInt();
		}
		
		// 최대 보수 계산
		for(int i = N; i > 0; i--) {
			int addTime = i + time[i];
		
			// 퇴사 후에 끝나는 경우
			if(addTime > N + 1) {
				memo[i] = memo[i+1];
			}
			
			// 퇴사 전에 끝나는 경우
			else {
				memo[i] = Math.max(memo[i+1], memo[addTime]+money[i]);
			}
			
		}
        
        // 최대 누적 보수
		System.out.println(memo[1]);
	}

}

⭐️ 느낀 점

• 최대한 풀어서 정리를 해보았으나 아직 미숙한 것 같습니다.