inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

코딩테스트 실전 모의고사(with C++) : 대기업 대비

4. 바둑대회 문제해설(DFS)

선생님, 제 코드 한번만 봐주실 수 있나요?

197

celestial_

작성한 질문수 72

0

강의 영상은 보지 않고 시간 재어서 풀었는데

왜 틀렸는지 잘 모르겠습니다... (정확하게는 시간초과가 나네요..)

이 문제는 풀만하다고 해서 잘 풀었던 것 같은데 

잘 모르겠습니다ㅜㅜ!! 

예제는 잘 나오고 개인적으로 테스트 케이스 몇개 돌려본 결과 

이상이 없는 것 같은데 고민을 해보고도 잘 되지 않아서 질문 올려봅니다.

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#define N 17

using namespace std;


int map[3][N];
bool visited[N];


int n;
int total = 0;
int level = 0;
int wtotal = 0;
int btotal = 0;
int ans = 0;
int mini = 10000;

void DFS(int total, int level) {

	if (level == n/2) {
		wtotal = total;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				btotal += map[2][i];
			}
		}


		ans = abs(wtotal - btotal);
		/*printf("wtotal : %d \n\n", wtotal);
		printf("btotal : %d \n\n", btotal);
		printf("ans : %d\n\n", ans);*/
		if (mini > ans) {
			mini = ans;
		}
		btotal = 0;


	}

	else {
		for (int i = 1; i <= n; i++) {

			if (!visited[i]) {
				visited[i] = true;
				total += map[1][i];
				level++;
				//printf("current total : %d level : %d\n\n", total, level);
				DFS(total, level);
				visited[i] = false;
				level--;
				total -= map[1][i];
			}

		}
	}

	


}



int main() {


	cin >> n;

	for (int i = 1; i <= n; i++) {
		int s, t;
		cin >> s >> t;
		map[1][i] = s;
		map[2][i] = t;
	}

	

	DFS(total, level);


	printf("%d ", mini);



}




감사합니다!! 

코테 준비 같이 해요! C++

답변 1

0

김태원

안녕하세요^^

타임리밋이 나는 이유가 위에 코드는 순열방식로 짜서 그렇습니다.

N명 중에서 N/2명을 뽑는 조합방식으로 짜야 타임리밋을 피할 수 있습니다.

0

celestial_

오 과연 조합 방식으로 복습 이후 풀어보니 ac 받았습니닼ㅋㅋㅋ 선생님 감사합니다!! 

조합을 구할때 algorithm 함수 next_permutation 사용 가능 여부

0

457

1

최악의 경우 연산 질문이 있습니다.

0

411

1

로컬 환경과 다르게 오답이라고 나와서 문의 드립니다.

0

302

1

6강 3번 정사각형 그리키 코드 질문 드립니다.

0

242

1

1-5 효율적인 공부 dy를 시간(N)으로 하는 풀이 질문

0

320

1

반복수와 시간초 계산을 어떻게 하나요??

0

333

1

왜 DP로 풀어야하는지 궁금합니다

0

242

1

선생님 안녕하세요. 다른 풀이에 대한 질문이 있습니다.

0

223

1

문제 해결방법에 대한 질문이 있습니다.

0

245

0

바둑대회 코딩 질문

0

270

1

6분 11초에서 dis [0][][]3차원 격자판이있는데요. 격자판안에 숫자는 문제에 없던데 어떻게 구해지는건가요?

0

200

0

실전모의고사 5회 1번 패턴찾기 질문있습니다.

0

220

1

전역변수관련 질문입니다.

0

255

1

5-1 패턴찾기 문제 질문드립니다.

0

218

1

오렌지 나무 문제 질문드립니다

0

310

1

코드 한번 봐주시면 감사하겠습니다!

0

175

1

코드 한번 봐주시면 감사하겠습니다!

0

234

1

코드 한번 봐주시면 감사하겠습니다!

0

198

1

시작점의 ch

0

204

1

vector에서 질문이 있습니다~!

0

235

1

그대로 따라했는데 시간 초과가 나왔습니다

0

161

1

2회 모의고사 4번 숲속의 기사 코드 질문이 있습니다.

0

288

1

질문있습니다.

0

209

1

이렇게 풀면 반례가 어떻게되나요?

0

245

1