문제
https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
개요
문제를 다 읽자마자 DP로 접근해야겠다는 생각이 들었다.
그래서 dp[i]를 'i번째 날까지의 최대 금액'으로 정한 후에, 점화식을 계속 생각해보았는데, 20분 넘게 떠올리지 못했다.
이차원 dp 배열을 이용한 접근도 시도했는데, 파고들수록 더 복잡해질 것 같았다.
그래서 결국 구글링한 후에 블로그 글을 참고하여 풀었다.
문제 풀이
이 문제의 핵심은 앞에서부터 생각하는 것이 아니라, 뒤에서부터 생각하는 것이다.
1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 | |
t[i] | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
p[i] | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
dp[i] |
만약 앞에서부터 생각한다고 해보자.
만약 1일차에 상담을 시작하게 된다면, t[i] = 3이므로 1일, 2일, 3일에 상담을 진행한다.
만약 2일차에 상담을 시작하게 된다면, t[2] = 5이므로 2일, 3일, 4일, 5일, 6일에 상담을 진행한다.
만약 3일차에 상담을 시작하게 된다면, t[3] = 1이므로 3일에만 상담을 진행한다.
앞에서부터 시작한 경우에, 3일차의 상담이 위의 3번의 경우에 모두 겹치는 상황이다.
그러면 이 3일차는 어느 경우에 포함되는 것이 가장 이득인지 알아내기 어렵다.
그러나, 만약에 뒤에서부터 시작한다면?
7일차부터 순서대로 4일차까지, 즉 4일차에 상담을 시작한 경우의 최대 금액을 구한 상태이다.
이 때, 3일차를 고려하는 경우는 단순한다.
3일차에 상담을 진행하는 경우 or 3일차에 상담을 진행하지 않는 경우 2가지만 고려하면 된다.
3일차에 상담을 진행하는게 이득일지, 진행하지 않는 게 이득일지는 두 가지의 값을 비교해야 한다.
1) 3일차에 상담을 진행했을 때가 더 최대 수익인 경우
→ 3일차에 상담을 진행했을 때의 가격(p[i])과, 3일차에 시작한 상담이 t[3]만큼의 시간이 걸려 완료된 후에 3 + t[3] = next 시점에 상담을 시작했을 때의 최대 가격(dp[next])의 합, 즉 p[i] + dp[next]
2) 3일차에는 상담을 진행하지 않고, 4일차에 상담을 진행했을 때가 더 최대 수익인 경우
→ 4일차에 상담을 시작했을 때의 최대 가격, 즉 dp[i + 1]
따라서, dp[i]는 dp[i + 1]과 p[i] + dp[next] 중에서 더 큰 값이 된다.
→ dp[i] = max(dp[i + 1], p[i] + dp[next])
1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 | |
t[i] | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
p[i] | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
dp[i] |
코드
#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector <int> t(n + 2); // 걸리는 기간
vector <int> p(n + 2); // 금액
vector <int> dp(n + 2); // i번째 날부터 고려 시 최대 금액
for (int i = 1; i <= n; i++) {
cin >> t[i] >> p[i];
}
for (int i = n; i > 0; i--) {
int next = i + t[i];
if (next > n + 1) { // i일차에 상담 시작했는데, 완료 기간이 n일차를 넘는 경우
dp[i] = dp[i + 1]; // i일차에는 상담 진행X, (i + 1)일차의 최대 금액 그대로 가져옴
}
else {
dp[i] = max(dp[i + 1], p[i] + dp[next]);
}
}
cout << dp[1];
return 0;
}
깨달은 점
DP 문제는 'DP로 풀면 되겠다!'라고 생각이 드는 것까지는 쉬운데, 정확한 점화식을 찾는 과정이 항상 어렵다.
이 문제와 같이 뒤에서부터 DP 점화식을 찾는 방식의 문제는 더더욱 어렵다.
DP 문제를 많이 풀면서 다양한 점화식을 접해보는 것이 중요할 것 같다.
'백준 문제 리뷰 > 삼성 SW 기출' 카테고리의 다른 글
[백준 14500] 테트로미노 (C++) - G4 (3) | 2023.09.27 |
---|---|
[백준 14503] 로봇 청소기 (C++) - G5 (0) | 2023.09.27 |
[백준 15686] 치킨 배달 (C++) - G5 (0) | 2023.09.24 |
[백준 14889] 스타트와 링크 (C++) - S1 (0) | 2023.09.23 |
[백준 14888] 연산자 끼워넣기 (C++) - S1 (0) | 2023.09.23 |
문제
https://www.acmicpc.net/problem/14501
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
개요
문제를 다 읽자마자 DP로 접근해야겠다는 생각이 들었다.
그래서 dp[i]를 'i번째 날까지의 최대 금액'으로 정한 후에, 점화식을 계속 생각해보았는데, 20분 넘게 떠올리지 못했다.
이차원 dp 배열을 이용한 접근도 시도했는데, 파고들수록 더 복잡해질 것 같았다.
그래서 결국 구글링한 후에 블로그 글을 참고하여 풀었다.
문제 풀이
이 문제의 핵심은 앞에서부터 생각하는 것이 아니라, 뒤에서부터 생각하는 것이다.
1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 | |
t[i] | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
p[i] | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
dp[i] |
만약 앞에서부터 생각한다고 해보자.
만약 1일차에 상담을 시작하게 된다면, t[i] = 3이므로 1일, 2일, 3일에 상담을 진행한다.
만약 2일차에 상담을 시작하게 된다면, t[2] = 5이므로 2일, 3일, 4일, 5일, 6일에 상담을 진행한다.
만약 3일차에 상담을 시작하게 된다면, t[3] = 1이므로 3일에만 상담을 진행한다.
앞에서부터 시작한 경우에, 3일차의 상담이 위의 3번의 경우에 모두 겹치는 상황이다.
그러면 이 3일차는 어느 경우에 포함되는 것이 가장 이득인지 알아내기 어렵다.
그러나, 만약에 뒤에서부터 시작한다면?
7일차부터 순서대로 4일차까지, 즉 4일차에 상담을 시작한 경우의 최대 금액을 구한 상태이다.
이 때, 3일차를 고려하는 경우는 단순한다.
3일차에 상담을 진행하는 경우 or 3일차에 상담을 진행하지 않는 경우 2가지만 고려하면 된다.
3일차에 상담을 진행하는게 이득일지, 진행하지 않는 게 이득일지는 두 가지의 값을 비교해야 한다.
1) 3일차에 상담을 진행했을 때가 더 최대 수익인 경우
→ 3일차에 상담을 진행했을 때의 가격(p[i])과, 3일차에 시작한 상담이 t[3]만큼의 시간이 걸려 완료된 후에 3 + t[3] = next 시점에 상담을 시작했을 때의 최대 가격(dp[next])의 합, 즉 p[i] + dp[next]
2) 3일차에는 상담을 진행하지 않고, 4일차에 상담을 진행했을 때가 더 최대 수익인 경우
→ 4일차에 상담을 시작했을 때의 최대 가격, 즉 dp[i + 1]
따라서, dp[i]는 dp[i + 1]과 p[i] + dp[next] 중에서 더 큰 값이 된다.
→ dp[i] = max(dp[i + 1], p[i] + dp[next])
1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 | |
t[i] | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
p[i] | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
dp[i] |
코드
#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector <int> t(n + 2); // 걸리는 기간
vector <int> p(n + 2); // 금액
vector <int> dp(n + 2); // i번째 날부터 고려 시 최대 금액
for (int i = 1; i <= n; i++) {
cin >> t[i] >> p[i];
}
for (int i = n; i > 0; i--) {
int next = i + t[i];
if (next > n + 1) { // i일차에 상담 시작했는데, 완료 기간이 n일차를 넘는 경우
dp[i] = dp[i + 1]; // i일차에는 상담 진행X, (i + 1)일차의 최대 금액 그대로 가져옴
}
else {
dp[i] = max(dp[i + 1], p[i] + dp[next]);
}
}
cout << dp[1];
return 0;
}
깨달은 점
DP 문제는 'DP로 풀면 되겠다!'라고 생각이 드는 것까지는 쉬운데, 정확한 점화식을 찾는 과정이 항상 어렵다.
이 문제와 같이 뒤에서부터 DP 점화식을 찾는 방식의 문제는 더더욱 어렵다.
DP 문제를 많이 풀면서 다양한 점화식을 접해보는 것이 중요할 것 같다.
'백준 문제 리뷰 > 삼성 SW 기출' 카테고리의 다른 글
[백준 14500] 테트로미노 (C++) - G4 (3) | 2023.09.27 |
---|---|
[백준 14503] 로봇 청소기 (C++) - G5 (0) | 2023.09.27 |
[백준 15686] 치킨 배달 (C++) - G5 (0) | 2023.09.24 |
[백준 14889] 스타트와 링크 (C++) - S1 (0) | 2023.09.23 |
[백준 14888] 연산자 끼워넣기 (C++) - S1 (0) | 2023.09.23 |