1R/2016 09 18 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:15Z

Repair pages found by live-compare batch 0001

← Older revision		Revision as of 14:46, 26 March 2026
Line 14:		Line 14:
	using namespace std;		using namespace std;

	int arr[12][12] = { 0, };		int arr[12][12] = { 0, };
	int dp[12][1 << 12] = { 0, };		int dp[12][1 << 12] = { 0, };
	int N;		int N;

	int TSP(int start, unsigned int mid, int dep) {		int TSP(int start, unsigned int mid, int dep) {
	if (dp[start][mid]) {		if (dp[start][mid]) {
	return dp[start][mid];		return dp[start][mid];
	}		}
	if (dep == 1) {		if (dep == 1) {
	dp[start][mid] = arr[start][0];		dp[start][mid] = arr[start][0];
	return arr[start][0];		return arr[start][0];
	}		}
	int ret;		int ret;
	dp[start][mid] = 11000000;		dp[start][mid] = 11000000;
	for (int i = 0; i<N; i++) {		for (int i = 0; i<N; i++) {
	if ((1 << i) & mid) {		if ((1 << i) & mid) {
	int tmp = TSP(i, mid - (1 << i), dep - 1);		int tmp = TSP(i, mid - (1 << i), dep - 1);
	if (tmp != 0 &&arr[start][i]) {		if (tmp != 0 &&arr[start][i]) {
	dp[start][mid] = min(dp[start][mid], arr[start][i] + tmp);		dp[start][mid] = min(dp[start][mid], arr[start][i] + tmp);
	}		}
	//printf("%d %d %d %u %d %d\n",dep, start, i, mid, arr[start][i] +tmp, dp[start][mid]);		//printf("%d %d %d %u %d %d\n",dep, start, i, mid, arr[start][i] +tmp, dp[start][mid]);
	}		}
	}		}
	if (dp[start][mid] == 11000000) {		if (dp[start][mid] == 11000000) {
	dp[start][mid] = 0;		dp[start][mid] = 0;
	return 0;		return 0;
	}		}
	return dp[start][mid];		return dp[start][mid];
	}		}

Line 50:		Line 50:
	mid = (mid << 1) + 1;		mid = (mid << 1) + 1;
	for (int j = 0; j<N; j++) {		for (int j = 0; j<N; j++) {
	cin >> arr[i][j];		cin >> arr[i][j];
	}		}
	}		}
Line 57:		Line 57:
	== 박인서 ==		== 박인서 ==
	#include <iostream>		#include <iostream>
	int w[11][11];		int w[11][11];
	bool visit[11] = { false, };		bool visit[11] = { false, };
	int min = 100000000;		int min = 100000000;

	void back(int s, int v, int n, int c,int cnt) {		void back(int s, int v, int n, int c,int cnt) {
	if (cnt == n && min > c + w[v][s] && w[v][s] != 0) {		if (cnt == n && min > c + w[v][s] && w[v][s] != 0) {
	min = c + w[v][s];		min = c + w[v][s];
	return;		return;
	}		}

	visit[v] = true;		visit[v] = true;
	for (int i = 0; i < n; i++) {		for (int i = 0; i < n; i++) {
	if (!visit[i] && min > c + w[v][i] && w[v][i] != 0)		if (!visit[i] && min > c + w[v][i] && w[v][i] != 0)
	back(s, i, n, c + w[v][i], cnt + 1);		back(s, i, n, c + w[v][i], cnt + 1);
	}		}
	visit[v] = false;		visit[v] = false;
	}		}

Line 80:		Line 80:
	for (int i = 0; i < n; i++) {		for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++)		for (int j = 0; j < n; j++)
	std::cin >> w[i][j];		std::cin >> w[i][j];
	}		}
	back(0, 0, n, 0, 1);		back(0, 0, n, 0, 1);
Line 104:		Line 104:

	== 곽정흠 ==		== 곽정흠 ==

175.124.46.11 at 04:38, 24 September 2016

2016-09-24T04:38:50Z

← Older revision		Revision as of 04:38, 24 September 2016
Line 91:		Line 91:
	= 아이디어 =		= 아이디어 =
	== 15이원준 ==		== 15이원준 ==
			* '다이나믹은 어려워'로 풀었습니다.
			* dfs로 탐색하고 중복되는 과정은 dp에 저장하여 풀었습니다.
	== 박인서 ==		== 박인서 ==
	* 백트래킹을 이용(시작점을 무조건 0번이라고 봐도 되는 이유는 순회이므로..)		* 백트래킹을 이용(시작점을 무조건 0번이라고 봐도 되는 이유는 순회이므로..)

175.124.46.11 at 04:37, 24 September 2016

2016-09-24T04:37:32Z

@@ Line 9: / Line 9: @@
 = 코드 =
 == 15이원준 ==
+ #include&lt;iostream&gt;
 == 박인서 ==
   #include &lt;iostream&gt;

165.194.27.163 at 04:46, 21 September 2016

2016-09-21T04:46:28Z

← Older revision		Revision as of 04:46, 21 September 2016
Line 55:		Line 55:
	** c : 현재까지의 비용		** c : 현재까지의 비용
	** cnt : 현재까지 방문한 도시 갯수		** cnt : 현재까지 방문한 도시 갯수
			* cnt가 n일 때 c의 값을 비교하여 최솟값을 구하면 됩니다.

	== 곽정흠 ==		== 곽정흠 ==

219.255.207.30 at 03:39, 21 September 2016

2016-09-21T03:39:24Z

@@ Line 5: / Line 5: @@
 = 참가자 =
+* 박인서
 = 코드 =
@@ Line 11: / Line 11: @@
 == 박인서 ==
 == 곽정흠 ==
@@ Line 18: / Line 48: @@
 == 박인서 ==
 == 곽정흠 ==

165.194.27.163: {CREATE}

2016-09-20T04:44:12Z

{CREATE}

New page

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/10971|외판원 순회 2]

= 참가자 =
*

= 코드 =
== 15이원준 ==

== 박인서 ==

== 곽정흠 ==

= 아이디어 =
== 15이원준 ==

== 박인서 ==

== 곽정흠 ==