글 읽기 - 반례 하나 들어주시면 감사하겠습니다.

legendmic2 4년 전 0

n이 10밖에 안되길래 next_permutation을 사용하여 모든 경우를 확인해보는 방식으로 진행했습니다.

질문게시판에 있는 반례를 확인해보고 제 코드를 보았는데, 어떤 부분에서 틀린건지를 모르겠습니다...ㅠㅠ

반례 하나 들어주시면 감사하겠습니다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n; cin >> n; // n = 도시의 수
	
	int W[10][10] = {};
	int temp = 0; // 현재 순열에서 계산될 총 비용
	int min = 1e9; // 지금까지의 순열들 중 가장 비용이 낮은 것

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> W[i][j];
		}
	}

	vector<int> curRoute(n);

	for (int i = 0; i < n; i++) {
		curRoute[i] = i;
	} // curRoute = {0, 1, 2, ...}

	do {
		temp = 0;
		for (int i = 0; i < n-1; i++) {
			if (W[curRoute[i]][curRoute[i + 1]] == 0) break;
			temp += W[curRoute[i]][curRoute[i + 1]];
		}
		temp += W[curRoute[n - 1]][curRoute[0]]; // 최종점에서 시작점으로
		if (temp < min) min = temp;
	} while (next_permutation(curRoute.begin(), curRoute.end()));

	cout << min << "\n";
	

}

pichulia 4년 전 2

반례는 잘 모르겠고..

35번째 줄에 길이 없으면 탐색을 중단하는데 그 다음 별다는 조치를 취하지 않고 바로 답이랑 비교를 하고 계십니다.

그리고 37번째 줄에서도 n-1번째랑 0번째 사이에 길이 없는 경우에 대한 고려도 안되있습니다.

0 1 0 0

0 0 1 0

0 0 0 1

1 0 0 0

이런 친구가 반려가 되겠네요

legendmic2 4년 전 0

@pichulia

너무나도 늦게 봐버렸네요... 말씀하신 부분 수정하니 해결됐습니다! 연말 잘 보내세요 감사합니다!!! :D

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 하나 들어주시면 감사하겠습니다.

legendmic2 4년 전 0

pichulia 4년 전 2

legendmic2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말