[C++] 백준(BOJ) - 1315 : RPG
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다.
게임에는 총 N개의 퀘스트가 있다. i번째 퀘스트를 깨려면 캐릭터의 힘이 STR[i]보다 크거나 같거나, 지력이 INT[i]보다 크거나 같아야 한다. 이 퀘스트를 깨면, 스탯을 올릴 수 있는 포인트를 PNT[i]개 만큼 얻게 된다.
모든 퀘스트는 단 한 번만 깰 수 있으며, 퀘스트를 깨는 순서는 준규가 마음대로 정할 수 있다. 또, 퀘스트 보상으로 얻게되는 포인트로 준규 마음대로 스탯을 올릴 수 있다.
준규가 깰 수 있는 퀘스트 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 퀘스트의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에 STR[i], INT[i], PNT[i]가 주어진다. 이 숫자는 모두 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 준규가 깰 수 있는 퀘스트 개수의 최댓값을 출력한다.
알고리즘
- DP
풀이
- 상태값 설정 : dp[힘][지능]
- dp의 특정상태일 때, max Quest수를 만들어 내면 정답
- 힘과 지능을 분배하는 모든 경우의 수를 구해야한다
- 방문처리 배열을 통해 원복을 하는 코드도 구현
코드
// BOJ - 1315 : RPG
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int n, q[54][3], dp[1004][1004];
bool visited[54];
// str, int를 상태값으로 설정
int cal(int a, int b)
{
if (dp[a][b] != -1) return dp[a][b];
int point = 0; // 레벨업 포인트 0으로 초기화
dp[a][b] = 0; // 퀘스트 수자 0부터 시작
vector<int> check;
for (int i = 0; i < n; i++)
{
if (q[i][0] <= a || q[i][1] <= b)
{
dp[a][b] += 1; // dp에 클리어한 퀘스트만 1개씩 더하기
if (visited[i]) continue; // 방문한 적 있으면 다음 퀘스트로 넘어가기 i++
point += q[i][2];
visited[i] = true;
check.push_back(i); // 방문처리를 체크하기 위한 vector
}
}
// 힘, 지능 분배하는 모든 경우의 수
for (int i = 0; i <= point; i++)
{
dp[a][b] = max(dp[a][b], cal(min(1000, a + i), min(1000, b + point - i))); // 최대 1000이므로 min함수 활용
}
// 원복
for (int i = 0; i < check.size(); i++)
{
visited[check[i]] = false;
}
return dp[a][b];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
memset(dp, -1, sizeof(dp)); // 답이 불가능한 -1로 dp배열 초기화
for (int i = 0; i < n; i++)
{
cin >> q[i][0] >> q[i][1] >> q[i][2];
}
cout << cal(1, 1);
return 0;
}
평가
- 완전탐색으로 풀 수 있지않을까 먼저 생각
- 1 ~ 1000까지 너무 경우의 수가 많다
- DP배열을 활용해 메모이제이션을 통해 구현
- DP 상태값 설정
- 문제에서 str, int 두 가지 상태 값에 의해 dp[a][b]값 체크할 수 있다
- 방문처리 배열 visited를 이용해 모든 퀘스트의 체크 여부를 확인
- 힘, 지능을 분배하는 모든 경우의 수를 max 함수를 이용해 재귀 호출
- 방문처리 배열을 원복하며 완전탐색 꼴을 만들어 준다
