글 읽기 - 반례를 못 찾겠습니다.도움 부탁드립니다.

thddudgns79 4년 전 0

재귀 완전탐색으로 구현했습니다.

11명의 선수들을 차례대로 돌면서 해당선수(DFS 함수의 index 매개변수)가 현재 맡을 수 있는 포지션을 다 세워보고 다음선수로 넘어가는 방식입니다.

어디서 잘못됐는지 잘 모르겠습니다. 도움 부탁드립니다.

import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	static boolean[] select;
	static int[][] stat;
	static int ans = -987654321;
	public static void main(String[] args) {
		int t = sc.nextInt();
		while(t > 0) {
			select = new boolean[11];
			stat = new int[11][11];
			for(int i = 0; i < 11; i++)
				for(int j = 0; j < 11; j++)
					stat[i][j] = sc.nextInt();
			dfs(0, 0);
			System.out.println(ans);
			t--;
		}

	}
	
	public static void dfs(int index, int sum) {
		// 마지막 선수까지 포지션이 확정되었다면 최댓값 갱신
		if(index == 11) {
			ans = Math.max(ans, sum);
			return;
		}	
		// 현재 인덱스의 선수가 맡을 수 있는 포지션 탐색
		for(int i = 0; i < 11; i++) {
			//해당 포지션이 아직 비었고 해당포지션 능력치가 0이 아닐 경우 선택
			if(!select[i] && stat[index][i] != 0) {
				select[i] = true;
				dfs(index + 1, sum + stat[index][i]);
				select[i] = false;
			}
		}
	}

}

pichulia 4년 전 4

ans 초기화가 안되고있습니다. 이전 답보다 현재 테스트케이스의 답이 더 작을 경우가 반례가 되겠네요.

2
0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0
0 0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 2 0 0
0 0 0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1

thddudgns79 4년 전 0

해결했습니다! 답변 정말 감사해요!!! ㅠㅠ

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다.도움 부탁드립니다.

thddudgns79 4년 전 0

pichulia 4년 전 4

thddudgns79 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말