3-P 질문 있습니다.

안녕하세요 항상 강의 잘 듣고 있습니다!

해당 문제를 풀면서 작성한 코드는 아래와 같습니다.

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[12][12];
int cost[12][12];
const int INF = 987654321;
int ret=INF;

void go(int cnt, int price, int start1, int start2){
	if(cnt==3) ret = min(ret, price);
	if(price>ret) return;
	
	for(int i=start1;i<=N-2;i++){
		for(int j= (i==start1? start2:1) ;j<=N-2;j++){
			if(arr[i][j] || arr[i-1][j] || arr[i][j-1] || arr[i][j+1] || arr[i+1][j]) continue; //이미 있는 경우
			arr[i][j]=1;
			arr[i-1][j] =1;
			arr[i][j-1] =1;
			arr[i+1][j] =1;
			arr[i][j+1] =1;
			int tmp_sum = cost[i][j]+cost[i-1][j]+cost[i][j-1]+cost[i+1][j]+cost[i][j+1]; 
			go(cnt+1, price+tmp_sum, i, j);
			arr[i][j]=0;
			arr[i-1][j] =0;
			arr[i][j-1] =0;
			arr[i+1][j] =0;
			arr[i][j+1] =0;
		}
	}
	return;
}

int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cin >> cost[i][j];
		}
	}
	
	go(0,0,1,1);
	
	cout << ret <<'\n';
	
	return 0;
}

처음에 작성한 코드는 go(0,0) 으로 x,y를 따로 파라미터로 넘겨주지 않았습니다. 하지만 이럴 경우 시간초과가 났습니다. 이로 인해 x, y 파라미터를 추가하였습니다.

실제로 해설 코드를 봐도 해당 인자를 넘기지 않는 것으로 확인되는데 이유는 모르겠으나 소요시간에 차이가 상당히 차이가 나는데 어떤 이유인지 알 수 있을까요?

답변 1

1

큰돌

2025-07-20T00:23:26.908Z

안녕하세요 우영님 ㅎㅎ

코드자체가 전반적으로 너무나도 잘 짜셨네요 ㅎㅎ

 

다만, return 부분이 빠진 것 같습니다.

기저사례 부분에서

	if(cnt==3) {
        ret = min(ret, price);
        return;
    }

이렇게 추가해보시겠어요?

0초로 저보다 더 빠른 것을 볼 수 있습니다.

 

---

 

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

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

감사합니다.

강사 큰돌 올림.