[백준/JAVA] 14501번: 퇴사
🔺 문제
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
🔺 코드
|
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
31
32
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] D = new int[N + 2]; // 오늘~퇴사일까지 벌 수 있는 최대 수입
int[] T = new int[N + 1]; // 상담에 필요한 일 수
int[] P = new int[N + 1]; // 상담 완료 시 받는 수입 저장 배열
for(int i = 1 ; i <= N ; i++) {
st = new StringTokenizer(br.readLine()," ");
T[i] = Integer.parseInt(st.nextToken());
P[i] = Integer.parseInt(st.nextToken());
}
for(int i = N ; i > 0 ; i--) {
// i번째 상담을 퇴사일까지 끝낼 수 있을 때
if((i + T[i] - 1) <= N) {
D[i] = Math.max(D[i + 1], D[i + T[i]]) + P[i]);
}
// i번째 상담을 퇴사일까지 끝낼 수 없을 때, 수입은 그대로
else {
D[i] = D[i + 1];
}
}
System.out.println(D[1]);
}
}
|
cs |
✅ 해결 아이디어
✔ DP - 점화식
→ dp[N] : N일에 얻을 수 있는 최대 수익
🔺 다른 풀이들
- 점화식이 약간 다르다. (DP 배열을 앞에서부터 채움)
[알고리즘/백준] 14051 퇴사 - 자바(Java), DP, 삼성 SW 역량테스트 기출
문제 https://www.acmicpc.net/problem/14501 풀이 코드 DP를 사용하여 풀이 dy[i] : i번째 날의 최대 수입 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public
developer-hm.tistory.com
[백준 14501] 퇴사 (자바)
백준 14501번 퇴사 (자바) 출처 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한
hidelookit.tistory.com
- 2차원 배열 점화식 & 재귀를 사용하셨다.
백준 14051 - 퇴사 · Yesdoing의 개발 블로그
사진을 클릭하시면 문제로 이동하실 수 있습니다. 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을
yesdoing.github.io
💬 느낀 점
재귀를 잘하고 싶구나...
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 7/5 |
(+7/3 2회독)
나름 점화식 비슷하게 쓴 거 같은데... 은근(?) 틀림
|
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
31
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] D = new int[N + 2];
int[][] arr = new int[N + 1][2];
for(int i = 1 ; i <= N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
for(int i = N ; i > 0 ; i--) { // 뒤에서부터 거꾸로~
if(i + arr[i][0] - 1 <= N) {
D[i] = Math.max(D[i+1], arr[i][1] + D[i + arr[i][0]]);
}
else {
D[i] = D[i + 1];
}
}
System.out.println(D[1]);
}
}
|
cs |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편