글 읽기 - 제 코드(백트래킹)의 시간 복잡도가 궁금합니다.

park780172 4년 전 0

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

정답 코드 주의

원래 처음에 풀었던 제 코드(http://boj.kr/97b6290ab87740c8b3d8b415e797605d)는 시간이 968ms나 걸렸습니다.

(처음 풀었던 코드의 의도는 한 점에 대해 여러 for문을 사용하여 직사각형 내에 존재하는 1의 합 구하기입니다. -1은 따로 계산.)

이유는 50*50이므로 이것을 백트래킹으로 하기에는 당연히 오래걸렸을 것이라고 생각했습니다.

그래서 어쩔 수 없이 시간이 빠른 다른 분의 코드를 봤더니 공식(?)을 활용하시거나 dp, knapsack, memoization 등으로 접근하셨더라구요.

하여튼 공식(첨부한 코드의 66, 69번 째 줄)을 제 코드에 적용하여 제출했더니 0ms가 나왔습니다.

무려 50*50을 백트래킹하기에는 오래 걸릴 것이라고 생각했었는데 0ms가 나와서 제가 생각한 시간 복잡도(2ⁿ또는 n!)와는 다른 것 같습니다.

제 코드의 시간 복잡도가 어떻게 되는지 궁금합니다.

첨부한 코드가 0ms 나온 코드입니다.

#include <bits/stdc++.h>

using namespace std;

#define Max 52

int R, C, K, m[Max][Max], t[Max][Max], sum;
bool use[Max][Max];

// 정답 출력(K의 배수인지 검사)
void chk(int s)
{
	if ((sum + s) % K == 0) {

		printf("1\n");
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (m[i][j] == -1) {
					printf("%d ", use[i][j] ? 1 : 0);
				}
				else {
					printf("%d ", m[i][j]);
				}
			}
			printf("\n");
		}

		exit(0); // 바로 종료
	}
}

// 백트래킹
void dfs(int r, int c, int s)
{	
	// K의 배수가 되는지 검사
	chk(s);

	if (c == C) {
		c = 0;
		++r;
	}

	if (r == R) {
		return;
	}

	if (m[r][c] == -1 && !use[r][c]) {
		use[r][c] = true;
		dfs(r, c + 1, s + t[r][c]);
		use[r][c] = false;
	}

	// 해당 칸(r, c)을 선택(덧셈) 안 할 때
	dfs(r, c + 1, s);
}

int main()
{
	cin.tie(0);

	scanf("%d %d %d", &R, &C, &K);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &m[i][j]);
			if (m[i][j] == 1) {
				sum += (i + 1)*(R - i)*(j + 1)*(C - j); // 공식
			}
			else if (m[i][j] == -1) {
				t[i][j] += (i + 1)*(R - i)*(j + 1)*(C - j); // 공식
			}
		}
	}

	// 백트래킹
	dfs(0, 0, 0);

	printf("-1\n");

	return 0;
}

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