알고리즘/코딩 테스트
[백준 1315] RPG - DP
Judith Hopps
2024. 2. 7. 10:57
https://www.acmicpc.net/problem/1315
1315번: RPG
준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다. 게임에는 총 N개의
www.acmicpc.net
시간 제한메모리 제한제출정답맞힌 사람정답 비율
| 2 초 |
128 MB |
4449 |
1126 |
735 |
25.026% |
문제
준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다.
게임에는 총 N개의 퀘스트가 있다. i번째 퀘스트를 깨려면 캐릭터의 힘이 STR[i]보다 크거나 같거나, 지력이 INT[i]보다 크거나 같아야 한다. 이 퀘스트를 깨면, 스탯을 올릴 수 있는 포인트를 PNT[i]개 만큼 얻게 된다.
모든 퀘스트는 단 한 번만 깰 수 있으며, 퀘스트를 깨는 순서는 준규가 마음대로 정할 수 있다. 또, 퀘스트 보상으로 얻게되는 포인트로 준규 마음대로 스탯을 올릴 수 있다.
준규가 깰 수 있는 퀘스트 개수의 최댓값을 구하는 프로그램을 작성하시오.
출력
첫째 줄에 준규가 깰 수 있는 퀘스트 개수의 최댓값을 출력한다.
제한)
n <= 50
0 <= STR[i], INT[i], PNT[i] <= 1000
2 초 128 MB
알고리즘)
재귀 (1,1) 시작
백트래킹...-> X
누락)
퀘스트를 깨는 순서는 준규가 마음대로 정할 수 있다 ...-> 정렬!!XX
순서 상관없음 -> for문으로 매번 확인!! -> visited
고난)
시간.........!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
이 문제를 DP로 풀어야 하는 이유!!
- for 시간 최적화, 중복 계산을 방지
- if 재귀, 54 * 1000 * 1000 *54*1000 --> 시간초과!!
더보기
int go(int visited, int STR, int INT)
{
int ret = 0;
for (int j = 0; j < N; j++)
{
if (!(visited & (1 << j)) && (STR >= S[j] || INT >= I[j]))
{
for (int i = 0; i <= P[j]; i++)
{
int newS = STR + i;
int newI = INT + P[j] - i;
if (newS > 1000 || newI > 1000)
continue;
ret = max(ret, go(visited | (1 << j), newS, newI) + 1);
}
}
}
return ret;
}
How?
- STR,INT로 결과값을 얻을 수 있으므로 이 두 개를 DP로 저장하자!
- 1,1 부터 시작해서 가능한 퀘스트에서 얻은 P를 합쳐서 다음으로 보내자
- visited로 저장하고 ret = max(ret,go(new,new)) , visited = 0으로 초기화하자
전체 코드
#include <bits/stdc++.h>
using namespace std;
int S[54], I[54], P[54], n, visited[54], dp[1004][1004];
int go(int STR, int INT)
{
int &ret = dp[STR][INT];
if (ret != -1)
return ret;
ret = 0;
int p = 0;
vector<int> temp;
for (int i = 0; i < n; i++)
{
if (S[i] <= STR || I[i] <= INT)
{
ret++;
if (!visited[i])
{
p += P[i];
visited[i] = 1;
temp.push_back(i);
}
}
}
for (int i = 0; i <= p; i++)
{
int nextSTR = min(1000, STR + i);
int nextINT = min(1000, INT + p - i);
ret = max(ret, go(nextSTR, nextINT));
}
for (int tt : temp)
{
visited[tt] = 0;
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> S[i] >> I[i] >> P[i];
}
memset(dp, -1, sizeof(dp));
cout << go(1, 1) << "\n";
return 0;
}