글 읽기 - 시간복잡도가 궁금합니다

rlawlgus322 3년 전 0

dfs로 모든 경우를 다돌아보게끔 했는데

저 부분에서 70줄과 81줄같이 기존 유죄수 배열을 저장하고 다시 업데이트 하는 부분에서 시간 초과가 일어날것이라고

생각했는데 통과하더락요

시간복잡도를 어떻게 계산하는 건지 궁금합니다.

처음 생각으로는

16명중 은지를 빼고 for문돌리는 횟수인 15 와

유죄수를 업데이트 하는 부분 for문에서에서 위에서 16명 중 마피아가 죽인 것을 빼면 15 그리고 그것이 2개있으니 *2..

낮에는 바로 선택하고 다음으로 넘어가기때문에 2사람씩없어진다생각하면

(15*(15* 2) )* (13*(13*2) )* (11*(11*2))*.... *(3*(3*2))

이렇게 나올거라 생각해 초과된다고 생각해서 다른 방법으로 계속풀다가 결국 이방법으로 푸니 되더라구요

이 문제는 시간복잡도를 어떻게 계산했어야되는걸까요

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static int[][] R;
	private static int eunj;
	private static int night = 0;
	private static int n;
	private static boolean[] visit;
	private static int[] guilty;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		if (n == 1) {
			System.out.println(0);
			return;
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		guilty = new int[n];
		R = new int[n][n];
		visit = new boolean[n];
		int mx =0;
		int mxidx =0;
		for (int i = 0; i < n; i++) {
			guilty[i]=Integer.parseInt(st.nextToken());
			if(guilty[i] > mx) {
				mxidx=i;
				mx = guilty[i];
			}
		}
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				R[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		eunj = Integer.parseInt(br.readLine());

		dfs(n, 0, n % 2,mxidx);
		System.out.println(night);

	}

	private static void dfs(int d, int day, int nord,int idx) {
		if (d == 1) {
			night = Math.max(night, day);
			return;
		}

		if (nord == 1) {// 낮
			if (idx == eunj) {// 마피아선택됨
				night = Math.max(night, day);
				return;
			}
			visit[idx] = true;
			dfs(d - 1, day, 0,-1);
			visit[idx] = false;
			
		} else {// 밤
			for (int i = 0; i < n; i++) {
				if (i == eunj || visit[i])
					continue;				
				visit[i] = true;
				// 유죄지수 변경
				int mx = 0;
				int mxidx =0;
				for (int j = 0; j < n; j++) {
					if(visit[j]) continue;
					guilty[j] +=R[i][j];
					if(guilty[j] > mx) {
						mxidx=j;
						mx = guilty[j];
					}
				}		
				
				dfs(d - 1, day + 1, 1,mxidx);
				
				for (int j = 0; j < n; j++) {					
					if(visit[j]) continue;
					guilty[j] -=R[i][j];
				}
				visit[i] = false;
				
			}
		}

	}
}

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

문제

문제

출처

ICPC

시간복잡도가 궁금합니다

rlawlgus322 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말