[JAVA] 14501번 - 퇴사

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

DP문제는 진짜 아무리 봐도 모르겠다 ㅜㅜ

일단 문제를 봤을때 고려해야하는건 다음과 같다.

1. 상담을 할지 말지 결정(1일차에 상담안하고 2일차에 상담하는게 더 나을수도 있으니까)

2. 상담했을때, 또 다른 상담을 할 수 있는지 확인

3. 상담안할때

 

DP로 접근할 수 있는 이유는 이렇다.

각 날 마다 상담을 할지 말지를 결정해야한다. 큰 문제를 작은 문제로 나눌 수 있음

그리고 각 선택이 이후 선택에 영향을 미친다 

 

DP배열을 만들어서 dp[i]는 i번째 날까지 얻을 수 있는 최대 이익을 나타낸다.

이 배열을 쓰면, 상담을 하고 얻는 이익을 계속해서 기록할 수 있기 때문이다. 

 

1. 상담을 할지 말지 선택

1) 상담을 하지 않고 다음 날로 넘어갈 때 이익 = 이전 날의 최대 이익을 그대로 유지 와 같은말이다

• dp[i + 1] = max(dp[i + 1], dp[i])

dp[i + 1]은 다음 날(i+1일)의 최대 이익

dp[i]는 현재(i일)의 최대 이익. 이 점화식은 다음 날로 넘어갔을 때 상담을 하지 않았을 경우, 이익이 그대로 유지된다는 것을 표현

 

2) i번째 날 상담을 진행할 경우: 상담이 끝난 이후 날의 이익을 갱신 

• dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i])

**dp[i + t[i]]**는 현재 상담이 끝난 후 그날까지의 최대 이익을 저장하는 값

**dp[i] + p[i]**는 i번째 날 상담을 한 후 얻은 이익. 즉, 현재 상담을 진행하고 나서의 이익을 계산한 값, i일까지 얻은 이익에 i일에 상담을 해서 추가로 얻은 금액을 더한 값

 

=>상담을 진행했을 때 이익과 기존에 저장된 이익을 비교하여 더 큰 값을 선택

즉 현재 상담을 진행한 후 이익이 더 큰지, 이미 계산된 이익이 더 큰지를 비교 

현재 상담을 진행하는 것이 더 이득이면 갱신하게 됨 

 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. dp배열을 만들고 입력을 받는다 

2. bottom-up 방식으로반복문 돌리면서 해결 

3. 출력

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

dp가 난 젤 어렵다...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

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[]t = new int[n+1];
        int[]p = new int[n+1];
        
        StringTokenizer st;
        
        for(int i=0; i<n; i++) {
        	st = new StringTokenizer(br.readLine());
        	t[i] = Integer.parseInt(st.nextToken());
        	p[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] dp = new int[n+1];
        
        for(int i=0; i<n; i++) {
        	if(i+t[i]<=n) { //날짜 초과x
        		//i번째날 상담했을때, 그 상담이 끝나는 날의 최대 이익 갱신 
        		dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
        	}
        	//상담 안하고 다음 날로 넘어가는 경우의 최대 이익 갱신 
        	dp[i+1] = Math.max(dp[i+1], dp[i]);
        }
        System.out.println(dp[n]);
        
    }
}