문제유형
문제태그는 DP와 브루트포스를 이용한 문제라고 되어있다.
DP의 성향이 강한 문제이며, 실버 3 난이도라고 보기에 어려운 문제였다...
✨ 문제해석
첫번쨰 줄에 N이 주어진다. N+1 일에 퇴사를 하므로, N일까지 일을 할 때 가장 많은 수당을 챙길 수 있는 금액을 구하는 문제이다.
두번째 줄부터는 t p가 주어진다.
▶ t-time 일을 하는데 걸리는 일 수
▶ p-pay 일을 하고 받는 수당
✨ 문제풀이
DP를 이용해서 1일차부터 N일차까지 일을 했을 때 챙길 수 있는 가장 큰 수당을 구하는 것이다.
Top-down으로 푸는 방법은 생각이 나질 않아서 Bottom-up으로 풀이.
문제 자체는 어렵지 않으므로 중요한 점을 먼저 강조한 뒤에 코드풀이를 하겠습니다.
① 일을 건너 뛰어서 할 때 더 큰 수당을 챙길수도 있다.
② 일을 하고 난 익일에 돈을 챙긴다는 개념으로 접근하여 풀이하였다.
- 10일차에 1일치를 일하면 11일째에 받으므로 DP라는 배열은 하나 더 크게 만들었다.
③ 구글링해서 나오는 풀이 중 절반 이상이 틀리다....
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader inputStr = new BufferedReader(new InputStreamReader(System.in));
int line = Integer.parseInt(inputStr.readLine());
int[] time = new int[line+1];
int[] pay = new int[line+1];
int[] dp = new int[line+2];
int max = 0;
String[] tmp;
for(int i = 1; i <= line; i++) {
tmp = inputStr.readLine().split(" ");
time[i] = Integer.parseInt(tmp[0]);
pay[i] = Integer.parseInt(tmp[1]);
}
for(int j = 1; j <= line + 1; j++) {
dp[j] = Math.max(max, dp[j]);
if(j <= line && j+time[j] <= line + 1) {
dp[j + time[j]] = Math.max(dp[j] + pay[j], dp[j + time[j]]);
}
max = Math.max(max, dp[j]);
}
System.out.println(max);
}
}✨ 코드풀이
① input이 들어오는 line 수를 먼저 입력 받는다.
② line 수만큼 time과 pay 배열을 +1만큼 선언하다. (n일차라는 것을 알기 쉽도록 +1을 했다.)
③ dp배열은 마지막 N일차의 일을 하고난 수당을 N+1일차에 받는다는 개념으로 접근했기에 +2
④ input을 입력받은 후 time과 pay 배열에 저장
--------------------------------아래는 반복문--------------------------------
⑤ dp[j]에는 앞에서 계산 후 저장한 값과 현재 최대값을 비교하여 저장한다.
즉, dp[j + time[j]] 로 저장된 값과 max값을 비교한다.
예제 2를 예시로 들면 1일차에는 0과 0을 비교 후 2일차에 1일차 수당을 저장.
2일차에는 1일차에서 저장한 2일차의 값과 max를 비교하여 저장⑥ 오늘 일해서 pay[j]를 더하는게 큰지, 앞에서 계산된 pay[j+time]가 큰지를 비교하는게 가장 큰 관건이다.
어떻게 해야 일을 건너뛰는 것을 비교할 수 있을 까 했는데 미래날짜에 값을 저장하고 미래날짜에 저장된 값을 비교하는 것이다.
예제 4의 1~5일차가 예시이다.
1일차에 일을 하면 5일차에 50을 받고 / 1일차를 건너뛰고 2일차에 일을 하면 5일차에 40을 받는다.
2일차에서 j+time[j] 의 값은 50이므로 40과 비교하면 50이 더 크기에 1일차에 일을 하는 것이 더 이득인 것으로 계산이 가능하다.
2번째로 어려웠던 부분은 건너뛰는 것을 감안하는 것이다.
예제 4를 예시로 들 때 7일차와 8일차의 경우인데, 7일차에 일을 하는 것보다 8일차에 일을 하는 것이 더 이득인데
7일차에 일을 했을 때 9일차에 받는 돈을 저장하고 / 8일차에 일을 했을 때 11일차(퇴사다음날정산)에 받는 돈을 각각 저장한 후 매번 max 값을 갱신하는 것이다. 이 케이스를 검증하기 위해 dp는 line보다 2를 크게 선언한다.⑦ max값을 출력
