[코딩테스트] 백준(BAEKJOON) - 퇴사(Java, 14501번)

안녕하세요.

이번에 풀어볼 문제는 너무나도 달달한 제목으로 저를 유혹한 '퇴사'라는 문제입니다.

 

사실 이번 문제는 정답률이 너무 높아 쉬울줄 알았는데 제 기준으로는 너무 어려웠습니다.

그래서 몇 번 틀리고 고민하다가 겨우 맞았네요~

 

일단 문제 만나보시죠~

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

그렇습니다. 주어진 일수 내에서 최대 수익을 얻어내야하는 문제입니다.

다음은 제가 작성한 코드입니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
			
			int count=Integer.parseInt(bf.readLine());
			int[]dp=new int[count+1];
			int max=0;
			for(int i=1;i<=count;i++)
			{
				//i는 포지션
				String[] data=bf.readLine().split(" ");
				int t=Integer.parseInt(data[0]);
				int p=Integer.parseInt(data[1]);
				if(i+t-1<=count)
				{
					
					dp[i+t-1]=Math.max(dp[i+t-1],p+dp[i-1]);
					max=Math.max(dp[i+t-1],max);
				}
				dp[i]=Math.max(dp[i], dp[i-1]);	
				
				
			}
	
			System.out.println(dp[count]);
		
	}

}

먼저 저 같은 경우에는 모든 입력값을 받아 처리하는게 아닌

입력값 받자마자 dp테이블을 구성하는 방식으로 진행했습니다.

 

그리고 i+t-1에 대해 설명을 하자면 첫째날 3일짜리의 상담을 한다고 생각하면~?

1(첫 째날)+3=4 즉 4번째에 숫자가 들어가는데 실질적 일은 세번째일에 마무리되고 네 번째부터는 새로운 일을 받을 수 있기에 -1을 통해 위치를 조금 수정해줬습니다.

 

또한 i+t-1<=count 조건은 제가 count넘어간 날짜는 어차피 백준이는 퇴사를 하고난뒤이니 볼필요도 없기에 생략했습니다.

 

우리는 dp[i]를 구하기 위해 생각해야될 경우가 두 가지가 있습니다.

case 1 : 이미 dp테이블 위치의 값이 지정된 경우

case 2: 이전 가치에서 T기간을 입력받았는데 그게 dp[i]일경우

 

즉 둘 중에 더 큰값을 넣어주면 최대 효율이 되겠습니다.

 

여기서 그러면 일을 안하는 날도 생깁니다. 그렇다고 가치가 사라지면 안되겠죠?

여전히 가치는 유지돼야하기에 이전 dp[i-1]의 가치를 가져와 값을 저장해주면 되겠습니다.

 

저는 이전값을 가져오는걸 생각하지 못해 꽤 걸렸습니다.

 

감사합니다. :D