8-B 질문 있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

8-B

작성

퀘스트를 한개씩 풀며 str, int를 비교하고 가능하면 point를 받아 이를 str과 int에 분배하며 최대한 많이 푸는 문제 이해서

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[a][b] = Math.max(dp[a][b], go(a, b)+1);
                    }
                    visited[i] = false;
                }
            }
        }

        return dp[STR][INT];
    }

이렇게 풀어야한다고 생각합니다.
즉
1번 퀘스트가 현재 능력치로 해결 가능하면
1. 방문처리
2. 그 포인트로 str, int에 분배하면서 다시 재귀

2 -1 . 현재 퀘스트를 해결한 것이니 go()재귀 다녀온 결과의 +1 함
3. 방문처리 해제

하지만 이렇게 접근하면 정답이 안되더라구요

왜 이 코드가 불가능한지 궁금합니다.

그래서 강사님 코드가 더더욱 이해가 가지 않습니다.

제가 문제를 잘 못 이해한건가요?
현재 str, int에서 최대한 한번에 해결할 수 있는 것을 모아서 한번에 해결하고 그 포인트를 모아서 분배하는 방법이 이해가 가지 않습니다. 포인트 분배는 마음대로니까 str, int 모두 point 분배를 전혀 안한 경우를 포함한 경우라고 생각하면 될까요?
이해가 가지 않는 코드부분은

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);
            }
        }
	}

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 ㅎㅎ

틀리신 전체 코드 부탁드립니다.(링크로 주시면 됩니다.)

감사합니다.

tjd125gns

질문자

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];
    }
}

큰돌

지식공유자

안녕하세요 ㅎㅎ

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

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

현재 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++ 코드로 부탁드립니다.

감사합니다.

인프런 커뮤니티 질문&답변

8-B 질문 있습니다.