출처: https://www.acmicpc.net/problem/1315
준상이는 새로운 RPG 게임을 시작했습니다. 이 게임의 특징은 다음과 같습니다:
캐릭터는 힘(STR)과 지력(INT) 두 가지 스탯을 가지고 있습니다.
캐릭터 생성 시 두 스탯은 모두 1입니다.
N개의 퀘스트가 존재하며, 각 퀘스트는 다음 조건을 만족해야 합니다:
캐릭터의 힘이 STR[i]보다 크거나 같거나
캐릭터의 지력이 INT[i]보다 크거나 같아야 합니다.
퀘스트 완료 시 PNT[i]개의 스탯 포인트를 얻습니다.
퀘스트는 한 번만 클리어할 수 있으며, 순서는 자유롭게 선택할 수 있습니다.
획득한 포인트로 원하는 스탯을 자유롭게 올릴 수 있습니다.
준상이가 클리어할 수 있는 최대 퀘스트 개수를 구하는 프로그램을 작성하세요.
입력 형식
첫째 줄에 퀘스트의 개수 N이 주어집니다. (1 ≤ N ≤ 50)
둘째 줄부터 N개의 줄에 걸쳐 각 퀘스트의 STR[i], INT[i], PNT[i]가 주어집니다.
모든 값은 1,000 이하의 자연수입니다.
출력 형식
클리어할 수 있는 최대 퀘스트 개수를 출력합니다.
예제 입력 1
5
1 1 2
3 1 1
1 3 1
10 20 5
3 3 1
예제 출력 1
4
예제 입력 2
2
1 1 1
2 2 2
예제 출력 2
2
import java.io.;
import java.util.;
public class Main {
// DP를 위한 배열들 선언
static int[][] questCount = new int[1001][1001]; // 각 스탯별로 클리어 가능한 퀘스트 수 저장
static boolean[][] dp = new boolean[1001][1001]; // 해당 스탯에 도달 가능한지 저장
static int[][] remaining = new int[1001][1001]; // 스탯 상승 후 남은 포인트 저장
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] quests = new int[n][3]; // STR, INT, POINT 정보 저장
// 퀘스트 정보 입력 받기 (STR, INT, POINT)
for(int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < 3; j++) {
quests[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(solveRpg(n, quests));
}
static int solveRpg(int n, int[][] quests) {
// 최대 스탯값 계산
int maxStr = ____; // 필요한 최대 힘 스탯
int maxInt = getMaxStat(quests, 1) + 1; // 필요한 최대 지능 스탯
// 시작 상태 설정
dp[1][1] = ____; // 초기 스탯(1,1) 방문 표시
// 가능한 모든 스탯 조합 탐색
for (int strStat = 1; strStat < maxStr; strStat++) {
for (int intStat = 1; intStat < maxInt; intStat++) {
int pointSum = 0; // 획득한 총 포인트
int cleared = 0; // 클리어한 퀘스트 수
// 현재 스탯으로 클리어 가능한 퀘스트 확인
for (int[] quest : quests) {
if (strStat >= quest[0] || intStat >= quest[1]) {
pointSum += ____; // 퀘스트 클리어 보상 획득
cleared++;
}
}
// 현재 스탯에서의 상태 저장
questCount[strStat][intStat] = cleared;
remaining[strStat][intStat] = pointSum - (strStat - 1) - (intStat - 1);
// 이전 상태에서 현재 상태로의 전이 가능성 확인
if (strStat > 1 && dp[strStat-1][intStat] && remaining[strStat-1][intStat] > 0) {
dp[strStat][intStat] = true;
}
if (intStat > 1 && dp[strStat][intStat-1] && remaining[strStat][intStat-1] > 0) {
dp[strStat][intStat] = true;
}
}
}
return getMaxClearedQuests(maxStr, maxInt);
}}
빈칸1: X
정답: getMaxStat(quests, 0) + 1
해설: 모든 퀘스트 중에서 필요한 최대 STR 스탯을 구하기 위해 첫 번째 열(인덱스 0)의 최댓값을 찾고 1을 더합니다. range가 끝값을 포함하지 않기 때문에 1을 더해야 모든 경우를 고려할 수 있습니다.
-> 나는 getMaxStat(quests, 1)으로 골랐다. 여기 부분을 잘 이해 못하고 찍었다. 인덱스 값이 추가되는 그런 개념으로 착각함.
빈칸2: X
정답: true
해설: 게임 시작 시점의 초기 스탯인 (1,1)은 반드시 도달 가능한 상태입니다. 이 값이 false라면 다른 스탯으로의 전이가 불가능하므로 초기값은 true여야 합니다.
-> 나는 0으로 골랐다. 그 이유는 dp 변수가 boolean 타입이라는것을 놓쳤다. 최근들어 계속해서 방심하고 뭔가 놓치는게 많다.
빈칸3: X
정답: quest[2]
해설: 퀘스트 배열의 세 번째 값(인덱스 2)이 해당 퀘스트를 클리어했을 때 얻을 수 있는 보상 포인트입니다. 이 포인트들의 합으로 스탯을 올릴 수 있는지 판단하게 됩니다.
-> 나는 quest[0] + quest[1]을 고름 인덱스가 커지는게 아니라 보상 받는다 해서 추가 되는 그런개념으로 착각함
