[백준 1315] RPG - DP

https://www.acmicpc.net/problem/1315

1315번: RPG

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

4449

1126

735

25.026%

문제

준규는 새 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보다 작거나 같은 자연수이다.

출력

첫째 줄에 준규가 깰 수 있는 퀘스트 개수의 최댓값을 출력한다.

 

제한)

    n <= 50

    0 <= STR[i], INT[i], PNT[i] <= 1000

    2 초 128 MB

알고리즘)

    재귀 (1,1) 시작

    DP

    백트래킹...-> 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;

}