[백준] 3980 선발 명단 - JAVA

백준 3980 선발 명단 Gold V - JAVA 📌

https://www.acmicpc.net/problem/3980

문제 설명

문제 풀이

---

접근 💡

요새 최적화에 관심이 많아져서 완전탐색을 떠올리지 않고 문제에 접근했던 것 같다.. 반성하고 자숙하자.. 모든 알고리즘의 시초는 완전탐색이다!!!

 

본론으로 들어가서

 

현재 선택하고 있는 포지션을다음 선수는 선택할 수 없을 때 포지션 점수의 최댓값을 구하는 문제이다.

모든 포지션을 선택했을 때 최댓값을 갱신해주면 되는 간단한 문제였다.

 

한 행(선수)의 포지션을 선택했을 때, 다음 행(선수)로 넘어가서 겹치지 않는 포지션을 선택하는 모~~~~~~~든 경우의 수를 구해 최댓값을 구하면 된다. 코드로 알아보자  

코드 💡

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

/**
 * 모든 경우의 수를 탐색하는 문제이다.
 * 현재 행에서 고른 포지션은 다음 행에서 고르면 안됨!. 그리고 0은 그냥 무시하기
 */
public class Main {

    static int[][] position;
    static boolean[] visited;
    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            position = new int[11][11];
            for (int i = 0; i < 11; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 11; j++) {
                    position[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            visited = new boolean[11];
            ans = 0;
            backTracking(0, 0);
            System.out.println(ans);
        }
    }

    private static void backTracking(int pos, int total) {
        if (pos == 11) {
            ans = Math.max(ans, total);
            return;
        }

        for (int i = 0; i < 11; i++) {
            if (!visited[i] && position[pos][i] != 0) {
                visited[i] = true;
                backTracking(pos + 1, total + position[pos][i]);
                visited[i] = false;
            }
        }
    }
}