2240번: 자두나무
자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어
www.acmicpc.net
DP에 아직 익숙하지 않구나를 느낄 수 있었던 문제였다.
[C++] 백준(BOJ) 2240 - 자두나무
- 문제 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는
1004dustkd.tistory.com
위 블로그에서 DP 힌트를 보지 않았다면 DFS, BFS로 풀려고 했을 것이다.
DFS나 BFS는 주로 그래프나 트리와 같은 구조에서 사용되는 탐색 알고리즘이지만, 이 문제는 단순한 그래프나 트리 구조가 아니다. 또한 자두의 위치는 시간에 따라 변하기 때문에 순차적으로 탐색하는 DFS나 BFS로는 이러한 시간적인 변화를 고려하기 어렵다.
그리고 T가 1000까지 늘어나기 때문에 완전탐색으로 한다면 2^1000까지 시간복잡도가 증가하기 때문에 완전탐색도 안된다.
그래서 DP를 선택하는 것이 맞는 선택이다
그러면 어떻게 DP를 적용할 수 있을까?
DP[위치][남은 걸음수][시간] 이런 데이터 포맷으로 계산값을 저장하면 된다.
위처럼 DP 시간, 위치, 남은 걸음 수 따른 자두 획득 개수를 기록해 놓으면 된다.
개수를 계산하는 방식을 위치를 옮길 때와 그대로 있는 경우다.
(l = 위치, w = 남은 걸음수, i = 시간)
*그대로 있을 때
1. 획득한 경우 => DP[l][w][i + 1] = max(DP[l][w][i + 1], DP[l][w][i] + 1)
2. 획득 못한 경우 => DP[l][w][i + 1] = max(DP[l][w][i + 1], DP[l][w][i])
* 위치를 옮길 때 (opp는 l의 반대)
1. 획득한 경우 => DP[opp][w - 1][i + 1] = max(DP[opp][w - 1][i + 1], DP[l][w][i] + 1)
2. 획득 못한 경우 => DP[opp][w - 1][i + 1] = max(DP[opp][w - 1][i + 1], DP[l][w][i])
따라서 위같은 원리로 코드를 작성하면
// 2240 자두나무
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int DP[3][31][1001]; // 위치, 걸음수, 시간
vector<int> loc;
int T, W, V;
int solve(){
DP[1][W][0] = 0;
for (int i = 0; i < loc.size(); i++){
for (int w = 0; w <= W; w++){
for (int l = 1; l < 3; l++){
if (DP[l][w][i] == -1)
continue;
// 그대로 가는 경우
if (l == loc[i + 1]) // 다음 스텝에서 내 자리에 자두가 떨어지는 경우
DP[l][w][i + 1] = max(DP[l][w][i + 1], DP[l][w][i] + 1); // 원래 있던 놈 vs 내가 지금 추가한놈
else{
DP[l][w][i + 1] = max(DP[l][w][i + 1], DP[l][w][i]);
}
// 옮기는 경우
if (w - 1 >= 0){
int opp = l == 1 ? 2 : 1;
if (opp == loc[i + 1]) // 다음 스텝에서 내 자리에 자두가 떨어지는 경우
DP[opp][w - 1][i + 1] = max(DP[opp][w - 1][i + 1], DP[l][w][i] + 1); // 원래 있던 놈 vs 내가 지금 추가한놈
else
DP[opp][w - 1][i + 1] = max(DP[opp][w - 1][i + 1], DP[l][w][i]);
}
}
}
}
int MAX = -1;
for (int w = 0; w <= W; w++){
for (int l = 1; l < 3; l++){
MAX = max(MAX, DP[l][w][T]);
}
}
return MAX;
}
void print(){
cout << " ";
for (int i = 0; i < loc.size(); i++){
cout << loc[i] << " ";
}
cout << endl;
for (int w = 0; w <= W; w++){
for (int l = 1; l < 3; l++){
cout << "l:" << l << ", w:" << w << ":";
for (int i = 0; i < loc.size(); i++){
cout << DP[l][w][i] << " ";
}
cout << endl;
}
}
}
int main(){
cin >> T >> W;
memset(DP, -1, sizeof(DP));
loc.push_back(1);
for(int i = 0; i < T; i++){
cin >> V;
loc.push_back(V);
}
cout << solve() << endl;
return 0;
}
이와 같은 코드가 나온다.
'코딩테스트' 카테고리의 다른 글
[프로그래머스 LV3 그래프] 순위 C++ (0) | 2024.03.05 |
---|---|
[백준 2212] 센서, C++ (0) | 2024.03.04 |
[백준 9527] 1의 개수 세기 C++ (0) | 2024.02.27 |
[SQL] 프로그래머스 : 재구매가 일어난 상품과 회원 리스트 구하기 (0) | 2024.02.20 |
[C++, 코딩테스트] 프로그래머스 : 의상 with 해시 (0) | 2024.02.16 |