Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- imeOptions
- Parcelable
- 지능형 기차2
- java
- 스카이라인 쉬운거
- 최단경로
- BuildConfig
- 백준 퇴사
- 백준 14501
- 조합
- 프로그래머스
- val
- 약수 구하기
- 시뮬레이션
- 완전탐색
- 자바
- EditorInfo
- 백준
- Kotlin
- SWEA
- hilt
- 순열
- 순수함수
- BFS
- EditText
- 2501
- Android
- 오르막수
- Parcelize
- dfs
Archives
- Today
- Total
안드 공부를 해볼까?
[Java] 백준 퇴사 본문
728x90
1. 문제분석
사실 이전에 퇴사2 문제를 먼저 풀고 풀어서 그런지 쉽게 풀었다.
퇴사 2에서는 구글링을 해도 이해가 안갔지만 하루동안 찾아보니 스스로 해결책을 알아버렸다.
일단 이 문제는 dp로 풀 수 있다. 만약 i일 때 일을 했다면 그 때 dp테이블의 값을 구하면 되는 것이니까.
노션에 이미 정리한 글이므로 복사해왔다. 그럼 하나씩 하기전에 2가지 조건을 세워서 해보자.
- 돈은 다음날 받는다.
- 예를 들어 1일날 일했으면 3일동안은 상담을 해야합니다.
- 그렇다면 1, 2, 3일은 다른 상담을 못하고 1일만의 상담을 해야합니다.
- 돈은 상담을 마치고 다음날에 들어오는 것으로 기준을 잡았습니다.(1일 → 4일)
- 내가 n일에 일했을 때, 나오는 값(점화식)
- 내가 1일에 일했다 → 4일부터 일 가능 → 4일까지의 최댓값 vs 1일까지 받은 돈 + 1일의 가치
- 내가 2일에 일했다 → 7일부터 일 가능 → 7일까지의 최댓값 vs 2일까지 받은 돈 + 2일의 가치
- 위와 같은 기준으로 나온 식은 dp[현재날짜 + 소요날짜] = dp[현재날짜 + 소요날짜] or dp[현재날짜] + 현재날짜의 가치
- 또한 현재 시점까지의 최댓값을 알기위해 max를 지속적으로 갱신한다.
※ max를 지속적으로 갱신하는 이유는 무엇일까?
일단 갱신하는 부분이 없다 생각하고 구해보겠습니다.
- dp[1 + 3] = Math.max(dp[1+3], dp[1] + p[1]) → dp[4] = Math.max(0, 0 + 10) → dp[4] = 10
- dp[2 + 5] = Math.max(dp[2+5], dp[2] + p[2]) → dp[7] = Math.max(0, 0 + 20) → dp[7] = 20
- dp[3 + 1] = Math.max(dp[3+1], dp[3] + p[3]) → dp[4] = Math.max(10, 0 + 10) → dp[4] =10
- dp[4 + 1] = Math.max(dp[4+1], dp[4] + p[4]) → dp[5] = Math.max(0, 10 + 20) → dp[5] = 30
- dp[5 + 2] = Math.max(dp[5+2], dp[5] + p[5]) → dp[7] = Math.max(20, 30+15) → dp[7] = 45
- dp[6 + 4] → 일수가 초과되므로 선택하지 않습니다.
- dp[7 + 2] → 일수가 초과되므로 선택하지 않습니다.
dp[7]에 지금 값이 나온 상태지만 우리의 기준은 다음날 돈을 받는다 입니다.
하지만 우리는 6일차 부터 새로운 일을 시작하지 못합니다. 결국 지난날 받았던 돈을 사용하는 것이죠.
이렇게 말해서도 잘 모르시겠다면 테스트케이스 3을 보겠습니다.(dp 테이블은 한번 구해보세요..!)
- 테스트 케이스 3은 10일까지 일할 수 있습니다.
- 1일에 (5,10) → 5일걸리고 10의 가치, 6일에 (5,10) → 5일걸리고 10의가치가 됩니다.
- 그래서 돈을 받는 날, 11일에 딱 20의 가치를 받을 수 있습니다. 이런식으로 구할 때는 max가 필요없습니다. 마지막에 최댓값이 나오게 되니깐요.
결과적으로 계산식 자체에는 크게 영향을 미치지 않지만 마지막 결과를 구할 때 값이 다르게 나옵니다.
2. 구현
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(br.readLine());
int[][] arr = new int[2][size + 2];
int[] dp = new int[size + 2];
for (int i = 1; i <= size; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[0][i] = Integer.parseInt(st.nextToken());
arr[1][i] = Integer.parseInt(st.nextToken());
}
int max = Integer.MIN_VALUE;
for (int i = 1; i <= size + 1; i++) {
if(max < dp[i]){
max = dp[i];
}
int time = i + arr[0][i];
if (time <= size + 1) {
dp[time] = Math.max(dp[time], max + arr[1][i]);
}
}
System.out.println(max);
}
}
size + 2를 해준 이유는 위에서 언급한대로 구현해준 것이다.(dp는 1부터 시작, 마지막 날 + 1까지)
3. 마무리
암만 생각해도 이게 퇴사2랑 다른게 뭘까..?
퇴사 2처럼 구현했는데 통과해버린 문제..
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[Java] 백준 치킨 배달 (0) | 2022.08.28 |
---|---|
[Java] 백준 연구소 (0) | 2022.08.27 |
[Java] 백준 스타트와 링크 (1) | 2022.08.27 |
[Java] 백준 안전 영역 (0) | 2022.08.21 |
[Java] 백준 단지번호붙이기 (0) | 2022.08.21 |
Comments