글 읽기 - 이 문제가 너무 풀고 싶은데 도와주세요;ㅂ;

thddudgns79 4년 전 0

재귀 이용해서 밤이면 현재 살아남은 시민을 한 명씩 다 죽여보고(경우의 수) 낮이면 글에서 나온 그대로 유죄점수 가장 높은 사람을 죽이는 방식으로 코드를 잤습니다.

근데 문제에 나온 테스트케이스를 돌리면 답이 2가 나와야하는데 0이 나와버립니다.ㅠㅠ

어디가 잘못된건지 계속 봐도 모르겠습니다. 도와주시면 감사하겠습니다

import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	// 대답
	static int[][] r;
	// 플레이어 수
	static int n;
	// 죽은 사람
	static boolean[] dead;
	// 플레이어별 유죄 점수
	static int[] score;
	// 가장 많이 지난 밤의 횟수
	static int ans = 0;
	
	public static void main(String[] args) {
		n = sc.nextInt();
		r = new int[n ][n];
		dead = new boolean[n];
		score = new int[n];
		for(int i = 0; i < n; i++) {
			score[i] = sc.nextInt();
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				r[i][j] = sc.nextInt();
			}
		}
		int player = sc.nextInt();
        //dfs(현재 살아남은 인원 수, 주인공(마피아)의 번호(인덱스), 밤이 지난 횟수)
		dfs(n + 1, player , 0);
		System.out.println(ans);

	}
	
	public static void dfs(int live, int player, int nightcount) {
		//플레이어 사망 경우
		if(dead[player]) {
			ans = Math.max(ans, nightcount);
			return;
		}
		// 주인공(마피아)가 마지막까지 살아남았을 경우
		if(live == 1) {
			ans = Math.max(ans, nightcount);
			return;
		}
		//밤
		if(live % 2 == 0) {
			for(int i = 0; i < n; i++) {
				// 살아남은 시민 죽이는 경우의 수
				if(!dead[i] && i != player) {
					dead[i] = true;
					// 유죄 점수 변화
					for(int j = 0; j < n; j++) {
						if(dead[j])
							continue;
						score[j] = score[j] + r[i][j];
					}
					
					//다음 단계
					dfs(live - 1, player, nightcount + 1);
					
					// 유죄 점수 되돌리기
					dead[i] = false;	
					for(int j = 0; j < n; j++) {
						if(dead[j])
							continue;
						score[j] = score[j] - r[i][j];
					}
				}
			}	
		}
		//낮
		else {
			// 유죄점수가 가장 큰 사람 중 낮은 번호인 사람 색출
			int maxvalue = score[0];
			int maxidx = 0;
			for(int i = 1; i < n; i++) {
				if(dead[i])
					continue;
				if(maxvalue < score[i]) {
					maxvalue = score[i];
					maxidx = i;
				}
			}
			// 죽이고 다음 단계
			dead[maxidx] = true;
			dfs(live -1, player, nightcount);
		}
	}

}

rlaeogh89 4년 전 0

전체적인 흐름은 맞는 것 같은데, 몇가지 오류가 있는 것 같습니다.

입력 받은 n은 참가자 수 입니다. n + 1 하면 참가자의 수를 증가시키는 것입니다.
밤에 시민을 죽일 때, dead[i] = false 는 점수 되돌리기를 진행한 후에 해야합니다.
낮에 유죄 점수가 높은 사람을 죽일 때, 이미 죽은 0번이 계속 죽는 경우가 생깁니다.
낮에 유죄 점수가 높은 사람을 죽이고 난 후에도 재귀가 끝나면 다시 살려야합니다.

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

문제

문제

출처

ICPC

이 문제가 너무 풀고 싶은데 도와주세요;ㅂ;

thddudgns79 4년 전 0

rlaeogh89 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말