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

안녕하세요 명운님 ㅎㅎ

이게 좀 특이한 문제인데 어차피 0 ~ 1000 까지의 int, str 부분만을 탐색한다.

즉 무한히 탐색하는것이 아니라 특정 범위만을 탐색하기 때문에 무한히 idx가 증가했을 때 그걸 처리하는 기저사례가 없어도 된다라고 보시면 됩니다.

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

이 코드를 보시면 일단 0 ~ 1000까지의 str, int 마다 함수가 호출될 것이라는것이 보이죠?

자 여기서

int rpg(int STR, int INT){
	int &ret = dp[STR][INT];
	if(ret != -1) return ret;

이렇게 이전에 방문했던 정점. 계산되었던 정점이라면 그냥 return 하는 것을 알 수가 있습니다.

이 부분에서 pnt가 0이더라도 계속 rpg() 함수를 호출할것 같은데

>>

아닙니다. pnt 가 모두 0일때를 가정하면 1, 1인 상태에서 해당 함수가 종료되어 더이상 함수호출은 일어나지 않습니다.

디버깅코드를 좀 넣어봤는데요. 이렇게 한번 해보시면 확인하실 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
struct game{
    int x, y, c; 
};
vector<game> a;
int n, dp[1001][1001];
bool visited[101]; 

int rpg(int STR, int INT){
    cout << STR << " : " << INT << "\n";
	int &ret = dp[STR][INT];
	if(ret != -1) return ret;

	ret = 0;
	int pnt = 0;
	vector<int> v;
	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 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 here : v)
        visited[here] = false;

	return ret;
}

int main(){
	scanf("%d", &n);
	for(int i=0; i<n; i++){
        int STR, INT, PNT;
		scanf("%d %d %d", &STR, &INT, &PNT);
        a.push_back({STR, INT, PNT});
	}
	memset(dp, -1, sizeof(dp));
	printf("%d\n", rpg(1, 1));
}

TC
5 1 1 0 3 1 0 1 3 0 10 20 0 3 3 0

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요 이명운 님, 인프런 AI 인턴이에요. 질문 주셔서 감사합니다.

선생님 코드를 보면, rpg() 함수가 재귀적으로 호출되는 부분에서 pnt가 0인 경우에는 p값에 따라서 STR과 INT를 갱신하는 것을 볼 수 있습니다. 따라서 pnt가 0일 때는 p 값이 0 일 때 한 번 호출되고 종료되게 됩니다.

이렇게 되는 이유는 for문의 조건에서 p는 0부터 pnt까지 반복되기 때문입니다. pnt가 0일 때는 p값도 0이기 때문에 반복문이 한 번만 실행되고 종료되게 됩니다.

따라서 rpg() 함수는 기저 사례가 있는 재귀 함수로서, pnt가 0인 경우에도 한 번 호출되고 종료되게 됩니다.

선생님의 코드를 참고하여 문제를 푸는데 이해가 어려운 부분이 있다면, 해당 부분을 선생님께 질문하여 더 자세한 설명을 받으시는 것을 추천드립니다. 감사합니다!