2024-10-27T00:08:56.077Z

0

Java 언어이지만 기본적인 배열과 list만 사용해서 이해하는데 어려움이 없을 것 같아 그대로 올리겠습니다.

백준에 제출해보니 1%이후 시간초과라는 결과가 나왔습니다.
나머지 예제들은 정상으로 나오지만 예제 1번 같은 경우 답이 4이지만 5가 나옵니다.

링크 : https://www.acmicpc.net/source/85680487

import java.util.*;
import java.io.*;

public class P1315 {
    static int n, arr[][], dp[][] = new int[1001][1001];
    static boolean visited[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        arr = new int[n+1][3];
        visited = new boolean[n+1];

        for (int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=0; j<3; j++) arr[i][j] = Integer.parseInt(st.nextToken());
        }

        for (int i=0; i<1001; i++)
            Arrays.fill(dp[i], -1);

        bw.write(go(1,1)+"");
        bw.flush();
        bw.close();
        br.close();
    }

    static int go (int STR, int INT) {
        if(dp[STR][INT] != -1) return dp[STR][INT];

        dp[STR][INT] = 0;
        int point = 0;
        ArrayList<Integer> list = new ArrayList<>();

        for (int i=0; i<n; i++) {
            if(arr[i][0] <= STR || arr[i][1] <= INT) {
                if(!visited[i]) {
                    visited[i] = true;
                    for (int j=0; j<=arr[i][2]; j++) {
                        int a = Math.min(1000, STR + j);
                        int b = Math.min(1000, INT+ arr[i][2]- j);
                        dp[STR][INT] = Math.max(dp[STR][INT], go(a, b)+1);
                    }
                    visited[i] = false;
                }
            }
        }

        return dp[STR][INT];
    }
}

0

안녕하세요 ㅎㅎ

자바로 링크를 주셔서요... 자바는 원래 답변드리지 않습니다.

먼저 이전 질문사항에 대한 답변은 다음과 같습니다.

현재 str, int에서 최대한 한번에 해결할 수 있는 것을 모아서 한번에 해결하고 그 포인트를 모아서 분배하는 방법이 이해가 가지 않습니다.

포인트 분배는 마음대로니까 str, int 모두 point 분배를 전혀 안한 경우를 포함한 경우라고 생각하면 될까요?

-> 네 맞습니다. 다음과 같이 STR에 0을 투자했을 때도 판단합니다.

	for(int p = 0; p <= pnt; p++){
        int nextSTR = min(1000, STR + p);
        int nextINT = min(1000, INT + pnt - p);
        ret = max(ret, rpg(nextSTR, nextINT)); 

	for(int i = 0; i < n; i++){
        if(a[i].x <= STR || a[i].y <= INT){
            ret++; 

앞의 코드는 지금의 포인트로 깰 수 있는 퀘스트라면 해당 갯수를++ 합니다.

            if(!visited[i]){
                visited[i] = true;
                pnt += a[i].c;
                v.push_back(i);
            }

이전 함수에서 방문을 안했는데 & 깰 수 있다면 -> 방문처리하면서 -> 해당 포인트를 추가합니다.

왜 시간초과가 날까요?

->

        for (int i=0; i<n; i++) {
            if(arr[i][0] <= STR || arr[i][1] <= INT) {
                if(!visited[i]) {
                    visited[i] = true;
                    for (int j=0; j<=arr[i][2]; j++) {
                        int a = Math.min(1000, STR + j);
                        int b = Math.min(1000, INT+ arr[i][2]- j);
                        dp[STR][INT] = Math.max(dp[STR][INT], go(a, b)+1);

지금 보시면 go라는 함수를 너무 많이 호출합니다. go함수 하나에 n * pnt만큼 호출되게 됩니다. 이부분을 줄여주셔야 합니다.

그리고 코드가 틀리는 이유는 저렇게 하면 이 STR, INT라는 DP의 의미 = 이 힘과 지력이 있을 때의 최대 퀘스트 갯수가 들어가는 의미가 깨지게 됩니다.

STR, INT를 기반으로 -> 깰 수 있는 최대 퀘스트 갯수를 카운팅하는 로직이 들어가야 합니다.

그리고 죄송하지만 원래 C++외의 언어 코드에는 답변드리지 않습니다.

다음부터는 C++ 코드로 부탁드립니다.

감사합니다.