BOJ31266 축구 대회(Java)

---

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

태그 : DP, 비트마스킹, 비트필드DP

---

사고 과정

DP 랜덤디펜스를 하다가 나온 문제이다.

11명 총합의 최대치를 구하는건 어렵지 않아보인다.

문제는 포지션별 최소 한 명인 조건, 골키퍼가 단 한 명일 조건이었다.

그래서 비트필드로 공격/중앙/수비 한 명씩이 채워졌는지 확인하고,

골키퍼는 dp 테이블을 하나 늘려 처리했다.

처음에는

DP[i][j][k][l] = i번째까지 j명 뽑았을 때 k비트로 표현되며 l로 골키퍼 유무를 확인할 때 최대 만족도.

코드를 짜다보니 인덱스가 전혀 필요 없는걸 느끼고,

dp[j][k][l]로 상태를 줄였다.

---

비트필드

static int [][][] dp = new int [12][8][2];

내가 선언한 dp 테이블인데,

j는 최대 11명이니 그렇다 치고, k번 테이블의 의미는

최대 3개의 비트에서, 각 비트가 켜져있으면 최소 한명 조건을 충족한 상황이다.

예로 비트가 101이라면 최소 공격수, 최소 수비수 조건은 달성한 상황이라는 것.

그리고 마지막 테이블로 골키퍼 유무를 잘 파악하면 된다.

---

코드

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int N;
    static int [] a = new int [200001];
    static int [] b = new int [200001];
    static int [] c = new int [200001];
    static int [] d = new int [200001];

    //2nd arr means bitmasks 101 -> forward1, middle0, defence1
    static int [][][] dp = new int [12][8][2];

    static int ans;

    static void solve() {

        for (int i = 1; i <= N; i++) {
            for(int j = 11; j > 0; --j) {
                for(int k = 0; k < 8; ++k) {

                    if (dp[j - 1][k][0] > 0) {
                        // 1. forward
                        dp[j][k | 4][0] = Math.max(dp[j][k | 4][0], dp[j - 1][k][0] + a[i]);

                        // 2. middle
                        dp[j][k | 2][0] = Math.max(dp[j][k | 2][0], dp[j - 1][k][0] + b[i]);

                        // 3. defence
                        dp[j][k | 1][0] = Math.max(dp[j][k | 1][0], dp[j - 1][k][0] + c[i]);

                        // 4. GK
                        dp[j][k][1] = Math.max(dp[j][k][1], dp[j - 1][k][0] + d[i]);
                    }

                    if (dp[j - 1][k][1] > 0) {
                        dp[j][k | 4][1] = Math.max(dp[j][k | 4][1], dp[j - 1][k][1] + a[i]);

                        dp[j][k | 2][1] = Math.max(dp[j][k | 2][1], dp[j - 1][k][1] + b[i]);

                        dp[j][k | 1][1] = Math.max(dp[j][k | 1][1], dp[j - 1][k][1] + c[i]);

                    }
                }
            }

            dp[1][4][0] = Math.max(dp[1][4][0], a[i]);
            dp[1][2][0] = Math.max(dp[1][2][0], b[i]);
            dp[1][1][0] = Math.max(dp[1][1][0], c[i]);
            dp[1][0][1] = Math.max(dp[1][0][1], d[i]);
        }

        ans = dp[11][7][1];
    }

    public static void main(String[] args) throws NumberFormatException, IOException {

        N = Integer.parseInt(br.readLine().trim());

        for (int i = 1 ; i <= N; ++i) {
            st = new StringTokenizer(br.readLine().trim());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
            c[i] = Integer.parseInt(st.nextToken());
            d[i] = Integer.parseInt(st.nextToken());
        }

        solve();

        System.out.println(ans);
    }
}

---

후기

브루트포스, 그리디를 이용한 풀이도 있다는 것 같다.

조금씩 성장하고 있을지도 ?