[코드트리] 10 - DP, 비트마스킹

문제 - 상하좌우 반전시키기 (lights off)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-filp-up-down-left-right-2/description

상하좌우 반전시키기 2 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[] board;
    static int[] temp;
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        board = new int[N];

        for(int i = 0; i<N; i++){
            int mask = 0;
            for(int j = 0; j<M; j++){
                if(read() == 1){
                    mask |= (1<<j);
                }
            }
            board[i] = mask;
        }

        int ans = INF;
        for(int m = 0; m < (1<<M); m++){
            temp = board.clone();
            int cnt = 0;

            // 마스크는 누른 상태를 나타내는거니까
            // c가 마스크에 존재하면 해당 버튼을 누른거임
            // 그러면 cnt++
            // -> cnt는 Integer.bitCount로 대체가능

            // j 순회 업는 버전
            int cur = m;
            // & ((1<<m)-1)로 j 경계 자동으로 잘려나감
            // 해결 : | | 로 하던거 xor로 연결, 인접해서 눌리면 중간 비트가 두번 xor됨
            // parity 고려해서 xor로
            int flip = ((cur<<1) ^ cur ^ cur>>1) & ((1<<M)-1);
            temp[0] ^= flip;
            if(N>1)
                temp[1] ^= cur;
            cnt += Integer.bitCount(cur);

            for(int i =1 ; i<N; i++){
                // 위 행에서 0인 위치를 1로 바꿔야하니까 
                // not으로 0/1 뒤집으면 1이 눌러야 할 위치가 되고 mask로 M개 비트만 유지
                int mask = ~(temp[i-1]) & ((1<<M)-1);

                if(mask != 0){
                    int flip2 = ((mask << 1) ^ mask ^ (mask >> 1)) & ((1<<M)-1);
                    temp[i] ^= flip2;
                    temp[i-1] ^= mask;
                    if(i < N-1)
                        temp[i+1] ^= mask;
                    cnt += Integer.bitCount(mask);
                }
            }

            if(temp[N-1] == ((1<<M)-1))
                ans = Math.min(ans, cnt);
        }

        System.out.print((ans == INF) ? -1 : ans);
    }
}

사고의 흐름 및 풀이

위 칸이 0이면 이걸 1로 바꿔주려면 바로 아래에서 칸을 눌러 1로 바꿔야 하고 그 행을 지나면 더이상 수정할 수 없음.

정답의 경우 모든 첫 행의 가능한 선택의 집합을 시도해보고 이 경우에 마지막 열에 도달했을 때 마스크의 상태가 

모든 비트 M개에 대해서 1일 때의 누적된 cnt의 값의 최소값이 정답임.

-> 바로 윗 칸의 상태가 결정되면 아랫 칸의 선택이 강제되므로 위-> 아래 열 방향으로 chasing

 

나도 처음에는 di,dj 배열을 잡아 열 비트마스킹 아이디어를 활용하며 board를 2차원 배열로 두고 
매번 j로 순회를 돌아 직접 copyBoard(temp)에 값을 업데이트함.

사실 입력 board의 경우 1과 0만 들어오므로 하나의 비트마스크로 볼 수 있고 M의 제한이 10이므로
따라서 board는 1차원 int형 배열로 압축할 수 있음.

 

여러 press가 겹칠 때 flip 횟수 홀짝성을 계산하기 위해 XOR를 활용하고
이때 j 경계 체크는 M개의 활성화된 비트와 AND 연산을 수행하면 자동으로 잘리기 때문에 경계 체크 명시적으로 안해도 됨.

 

press 할때마다 원래는 cnt를 1씩 증가시켰지만 자바의 경우 Integer.bitCount 함수를 활용하여
mask 자체가 누르는 경우를 표현하는 것이므로 1의 갯수를 세서 한번에 계산함

시간 복잡도는 첫 행 모든 경우 수행 -> 2^M번, 각 mask 마다 cloning O(N), 비트연산은 O(1)이므로

전체 시간 복잡도는 2^M * N, 공간 복잡도는 각 행을 마스크 하나로 저장하니 O(N)

---

문제 - N*M을 2*1, 1*2 로 채우기 (Broken Profile DP, 타일링)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rectangle-fill-6/description

사각형 채우기 6 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static int N,M;
    static int[][] dp;
    static final int MOD = 10_007;

    static void dfs(int row, int cm, int nm, int col, int ways){
        // 다 채움
        if(row == N){
            dp[col+1][nm] = (dp[col+1][nm] + ways) % MOD;
            return;
        }

        // 만약 현재 상태의 row가 채워져 있으면 다음 row
        if((cm & (1<<row)) != 0){
            dfs(row+1, cm, nm, col, ways);
            return;
        }

        // 가로 채우기
        dfs(row+1, cm | (1<<row), nm | (1<<row), col, ways);
        // 세로 채우기
        if(row+1 < N && ((cm & (1<<(row+1))) == 0)){
            dfs(row+2, cm | (1<<row) | (1<<(row+1)), nm, col, ways);
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        dp = new int[M+1][1<<N];
        dp[0][0] = 1;

        for(int i = 0; i<M; i++){
            for(int mask = 0; mask < (1<<N); mask++){
                if(dp[i][mask] == 0)
                    continue;
                dfs(0, mask, 0, i, dp[i][mask]);
            }
        }

        System.out.print(dp[M][0]);
    }   
}

사고의 흐름 및 풀이

세로가 n, 가로가 m인 면적을 1*2, 2*1 타일로 채우는 경우의 수를 10_007로 나눈 결과를 구하는 문제이다.

1*2 타일은 가로로 놓았을 때는 현재 col과 col+1를 점유하며 세로로 놓았을 때는 col만 점유한다.

완성되는 시점 말고 타일 자체를 놓은 상태를 전부 따진다는 아이디어로 접근해보자.

 

세로 갯수가 N개이고 가능한 방법은 가로로 놓기, 세로로 놓기 2가지이므로 비트마스킹으로 표현하면 1<<N 가지가 존재한다.

그리고 현재 처리되는 위치를 0 (아무것도 안놓은 상태) ~ M 이라 하면 인덱스상으로는 M으로 나오려면 M+1로 크기를 잡는다.

그럼 모두가 처리된 상태는 dp[M][0] 이 된다. 

-> M-1번 열까지 완전히 처리하고 M번 열을 채우려하는데 M번 열에는 채워진게 없는 상태

-> M-1까지밖에 없으니 완전히 채운 상태를 의미함.

 

DP 전이 및 초기화

dp[colPos][curMask] = 현재까지 타일이 놓인 가로 위치이가 colPos일 때,
그 col 상의 타일이 놓인 상태가 curMask일 때의 경우의 수를 MOD로 나머지 연산한 결과

아무것도 놓여있지 않은 상태는 공집합 1가지이므로 dp[0][0] = 1로 초기화하고

colPos = [0, M-1], mask = [0, (1<<N)-1] 로 순회한다.

만약 dp[i][mask] 가 0이라면 도달할 수 없는 상태이므로 상태 전이를 할 수 없다.

 

DFS

열 = 가로 (M), 행 = 세로 (N)

현재 열을 모두 채우면서 그 결과 다음 열의 상태를 만드는 것이 dfs의 역할이다. 

파라미터 : 현재 처리중인 세로 방향 idx, 현재 마스크 상태, 다음 마스크 상태, 현재 처리중인 가로 방향 idx, 경우의 수

 

1) 현재 행에서 모든 열이 처리됨

-> 다음 열로 넘어가고 경우의 수를 갱신해야 함

-> dp[col+1][nm] += ways

 

2) 현재 열이 이미 점유되어 있음 

-> (cm & (1<<row)) != 0이면 다음 행으로 넘어가야 함

-> dfs(row+1, cm, nm, col, ways)

 

3) 타일을 놓음

타일을 놓을 때 col이 변동되지 않는 이유는 col은 지금 내가 완전히 채우려고 작업중인 열 번호이지 닿는 번호가 아님.

 

3-1) 가로로 타일을 놓음

-> 현재 열에서 타일을 놓으면 길이가 2니까 다음 열에 있는 nm에 영향이 가게 되고 같은 행에서 이루어져야 한다.

현재 열(row 위치) + 다음 열(row 위치)를 점유하는 상태임

-> dfs(row+1, cm | (1<<row), nm | (1<<row), col, ways)

 

3-2) 세로로 타일을 놓음

-> 현재 행에서 타일을 세로로 놓으면 N 범위 내이어야 하고 해당 열에 점유된 타일이 있으면 안된다.

row +1 < N 이며 (cm & (1<<(row+1)) == 0)

-> dfs(row+2, cm | 1<<row | 1<<row+1, nm, col, ways)

-> nm이 영향을 안 받는 이유는 세로로 놓으면 row, row+1을 점유하게 되고

그 열 안에서 끝나기 때문에 next mask는 갱신하지 않아도 된다.

---

문제 - 물체 놓기(TSP, 최소비용 구하는 문제) (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-place-object-2/description

물체 놓기 2 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N, K;
    // 간선 cost와 물건 직접놓는 cost는 분리해야함..
    // dp 갱신할때 역할이 달라서
    static int[] thingCost;
    static int[][] cost;
    static int[] dist;
    static final int INF = 100_000 * 32;

    static void tsp(){
        dist = new int[1<<N];
        Arrays.fill(dist, INF);
        // 모든 점에서 시작가능함
        for(int i = 0; i<N; i++){
            dist[1<<i] = thingCost[i];
        }

        for(int m = 0; m<(1<<N); m++){
            for(int has = 0; has < N; has++){
                if(dist[m] == INF)
                    continue;
                if((m & (1<<has)) == 0)
                    continue;
                for(int hasNot = 0; hasNot < N; hasNot++){
                    if((m & (1<<hasNot)) != 0)
                        continue;
                    if(cost[has][hasNot] == 0)
                        continue;
                    int nm = m | (1<<hasNot);
                    // 없는 점을 집합에 추가할때 cost는 
                    // 1) 기존 집합에서 간선으로 새 물체를 연결하기
                    // 2) 기존 집합에 추가로 새 물체를 직접 놓기
                    int add = Math.min(cost[has][hasNot], thingCost[hasNot]);
                    dist[nm] = Math.min(dist[nm], dist[m]+add);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        K = read();
        thingCost = new int[N];
        cost = new int[N][N];
        for(int i = 0; i<N; i++){
            thingCost[i] = read();
        }
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                cost[i][j] = read();
            }
        }

        // 근데 플로이드를 하면 중간 정점이 압축되어버려서 중간정점이 mask에서 빠지는데 이게 왜??
        // 문제 조건때문에 괜찮음. 다만 DP 정의 변경됨
        for(int k = 0; k<N; k++){
            for(int i = 0; i<N; i++){
                for(int j = 0; j<N; j++){
                    if(cost[i][k] != 0 && cost[k][j] != 0){
                        cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                    }
                }
            }
        }

        tsp();
        int ans = INF;
        for(int m = 0; m< (1<<N); m++){
            if(Integer.bitCount(m) >= K){
                ans = Math.min(ans, dist[m]);
            }
        }
        System.out.print(ans);
    }
}

정리

어떤 정점들에 물체를 최소비용으로 놓고 싶은데 직접 놓는 비용이 있고 이미 있는 물체에서 간선을 연결하면 물체가 생김. 

두가지 방법으로 놓을때 최소 K개 이상의 칸에 물체를 놓을때의 최소 비용 구하기

-> 정답은 Integer.bitCount로 이게 K 이상이면 dist[m]으로 최소 갱신하기

 

플로이드 전처리

최소 비용을 구한다면 어떤 정점에서 정점으로 가는 최소 비용이 있으면 그걸 쓰는게 유리하다.

근데 플로이드를 하게 되면 a->k, k->b 가 가능하고 이게 더 적으면 a->b가 갱신되는데 이건 물체 집합으로 보면

a,k,b이고 k=3이다. 그런데 문제 조건에서는 K개 이상이기 때문에 플로이드에 의해 경유 정점이 추가되어 정확히 K개는 아니게 되어 기존 DP 정의에서는 어긋날 수 있지만 이때 정의되는 DP정의에서는 올바른 상태가 된다.

따라서 이렇게 상태를 압축해도 최소비용은 변하지 않는다.

 

DP 정의 및 초기화

TSP로 푸는데 맨 처음에 아무 정점에서나 시작할 수 있기 때문에 직접 놓는 비용으로 1<<i 마스크마다 시작 비용을 초기화함

여기서는 한번씩만 방문해야한다는 조건도 없으니 현재 집합에 새로운 요소를 추가한다는 관점으로 해야함 

-> dist[ mask ] = 현재 정점 집합이 포함하는 요소가 mask 일 때 드는 최소 비용

-> 플로이드를 쓰면 dist[ mask ] = 현재 정점 집합의 필요조건이 mask 일 때 드는 최소 비용 

 

전이 조건

1) dist[ mask ] 가 유효한 값을 지녀야 함

2) has (이미 있는 정점) 이 현재 마스크에 포함되어있어야 하고

3) hasNot (추가하려는 정점) 이 현재 마스크에 포함되어있으면 안되고

4) has -> hasNot 을 연결하는 간선 비용이 0이 아니어야 함 (문제 조건에서 0이면 간선 이동 못하는거임)

-> 비용은 1) 직접 놓는 비용 2) 간선으로 연결할때의 비용 두가지를 비교해서 그 중 최소

---

문제 - 모든 숫자가 등장하는 수 (계단수 dp)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-the-number-of-occurrences-of-all-digits/description

모든 숫자가 등장하는 수 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static final int MOD = 10_007;

    public static void main(String[] args) throws IOException{
        int N = read();
        if(N < 10){
            System.out.print(0);
            return;
        }

        // N번째 자리까지 봤고 현재 집합 상태 m, 마지막으로 고른 숫자가 j인 상태에서 경우의 수
        int[][][] dp = new int[N+1][1<<10][10];
        for(int s = 1; s<10; s++){
            dp[1][1<<s][s] = 1;
        }

        for(int pos = 2; pos<=N; pos++){
            for(int m = 0; m<(1<<10); m++){
                for(int i = 0; i<10; i++){
                    if(i > 0){
                        int nm = m | 1<<(i-1);
                        dp[pos][nm][i-1] = (dp[pos][nm][i-1] + dp[pos-1][m][i]) % MOD;
                    }
                    if(i < 9){
                        int nm = m | 1<<(i+1);
                        dp[pos][nm][i+1] = (dp[pos][nm][i+1] + dp[pos-1][m][i]) % MOD;
                    }
                }
            }
        }

        int ans = 0;
        for(int i = 0; i<10; i++)
            ans = (ans + dp[N][(1<<10)-1][i]) % MOD;
        System.out.print(ans);
    }
}

문제 원문

N자리인 자연수 중 0부터 9까지의 숫자가 전부 등장하면서 인접한 숫자간의 차가 전부 1인 서로 다른 자연수의 개수를 구하는 프로그램을 작성해보세요. 단, 0으로 시작하는 수는 세지 않음에 유의합니다.

 

DP 정의 및 초기화

쓸수 있는 숫자는 [0, 9]이고 N자리이므로

dp[N+1][1<<10][10] = 1-based N자리까지 봤을 때 현재 숫자의 구성 요소가 mask이고
마지막으로 선택한 숫자가 i 일 때 경우의 수에다가 MOD 나머지 연산을 수행한 값

초기화는 1번째 자리에서는 0으로 시작하지 못하기 때문에 i = [1, 9] 로 dp[1][1<<i][i] = 1임

마지막으로 본 숫자를 i라고 할 때 i>0 일때만 i-1로 전이할 수 있고, i<9 일때만 i+1로 전이할 수 있음

---

문제 - TSP 3

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-taveling-salesman-problem-3/description

외판원 순회 3 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,K;
    static int[][] cost;
    static final int INF = 16*10_000 + 1;
    static int[][] dist;
    
    static void tsp(){
        dist = new int [1<<N][N];
        for(int i = 0; i<(1<<N); i++)
            Arrays.fill(dist[i], INF);
        dist[1<<0][0] = 0;

        for(int m = 0; m<(1<<N); m++){
            for(int last = 0; last < N; last++){
                if(dist[m][last] == INF)
                    continue;
                if((m & (1 << last)) == 0)
                    continue;

                for(int next = 0; next < N; next++){
                    if((m & (1 << next)) != 0)
                        continue;
                    if(cost[last][next] == 0)
                        continue;
                    int nm = m | (1<<next);
                    if(dist[nm][next] > dist[m][last] + cost[last][next]){
                        dist[nm][next] = dist[m][last] + cost[last][next];
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        K = read();
        cost = new int[N][N];
        for(int i= 0; i<N; i++){
            for(int j = 0; j<N; j++){
                cost[i][j] = read();
            }
        }

        tsp();

        int ans = INF;
        for(int m = 0; m< (1<<N); m++){
            if(Integer.bitCount((m>>1)) == K){
                for(int i = 1; i<N; i++){
                    if(dist[m][i] == INF)
                        continue;
                    if(cost[i][0] == 0)
                        continue;
                    ans = Math.min(ans, dist[m][i]+ cost[i][0]);
                }
            }
        }
        System.out.print(ans);
    }
}

문제 원문 

1번 지점에서 출발하여 1번 지점을 제외하고 정확히 K개의 지점을 딱 한 번씩만 방문하고 다시 1번 지점으로 돌아오려고 합니다. i번 지점에서 j번 지점으로 이동하는 데 드는 비용 정보 Aij​가 주어졌을 때, K개의 정점을 겹치지 않게 방문하고 되돌아오는데 필요한 최소 비용의 합을 구하는 프로그램을 작성해보세요.

 

풀이 : 0-based로 바꿔서 tsp해주고 i->0 cost가 0이 아니고 dist[mask][i]가 invalid 하지 않을 때 ans를 최소로 갱신하기

---

문제 - 인접한 칸 선택(열단위 비트마스킹, 인접 동서남북 확인)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-pick-adjacent-cells-2/description

인접한 칸 선택 2 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int[][] board;
    static int N,M;

    static int getSum(int col, int m){
        int sum = 0;
        for(int i= 0; i<N; i++){
            if((m & (1<<i)) != 0){
                sum += board[col][i];
            }
        }
        return sum;
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();

        board = new int[M][N];
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                board[j][i] = read();
            }
        }

        int[][] cost = new int[M][1<<N];
        for(int i = 0; i<M; i++){
            for(int m = 0; m< (1<<N); m++){
                cost[i][m] = getSum(i, m);
            }
        }

        int[][] dp = new int[M][1<<N];
        for(int m = 0; m<(1<<N); m++){
            if((m & (m<<1)) != 0)
                continue;
            dp[0][m] = cost[0][m];
        }

        int ans = 0;
        for(int i = 1; i<M; i++){
            for(int m = 0; m<(1<<N); m++){
                if((m & (m<<1))!= 0)
                    continue;

                for(int prev = 0; prev<(1<<N); prev++){
                    if((m & prev) != 0)
                        continue;
                    dp[i][m] = Math.max(dp[i][m], dp[i-1][prev] + cost[i][m]);
                    if(i == M-1){
                        ans = Math.max(ans, dp[i][m]);
                    }
                }
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

n×m 크기의 격자 정보가 주어집니다. 각 칸에는 하나의 정수 값이 적혀있습니다. 선택된 칸에 적혀있는 수들의 합이 최대가 되도록 선택하되 상하좌우로 인접한 칸이 동시에 선택되지는 않도록 하는 프로그램을 작성해보세요.

여기서 n은 최대 10이고 m은 최대 100이므로 기존 비트마스킹 dp처럼 그대로 board를 쓸 순 없음. 

-> 가로 세로 바꿔서 입력받고 그대로 활용함 (최대 합을 구하는 거라 모양 자체는 아무래도 상관없음)

정답은 M-1번째 줄을 갱신할때 최대값을 받아서 출력

 

상하좌우 인접 조건 체크

위->아래, 왼->오 로 전파해나가는 DP이기 때문에 아래쪽은 체크할 필요 없음. (위쪽 체크하면 알아서 체크됨)

좌우 인접은 (m & (m<<1) == 0) 하고 (m & (m>>1) == 0)로 체크해야할 것 같지만 사실 한쪽만 체크해도 가능함 

여기서는 왼->오로 전파하기 때문에 (m & (m << 1) == 0) 일때만 전파함

 

위 인접은 prevMask -> curMask의 형태로 전이하기 때문에 prev와 mask를 AND 연산한 결과가 0이 아니라면 

위로 겹치는 칸이 존재한다는 의미이기 때문에 이걸로 체크 가능함.

---

문제 - 인접한 칸 선택 3 (3차원 DP)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-pick-adjacent-cells-3/description

인접한 칸 선택 3 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M,K;
    static int[][] board;
    static int[][] cost;

    static int getSum(int row, int m){
        int sum = 0;
        for(int j =0; j<M; j++){
            if((m & (1<<j)) != 0){
                sum += board[row][j];   
            }
        }
        return sum;
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        K = read();
        board = new int[N][M];
        cost = new int[N][1<<M];
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                board[i][j] = read();
            }
        }
        for(int i = 0; i<N; i++){
            for(int m = 0; m<(1<<M); m++){
                if((m & (m<<1)) != 0)
                    continue;
                cost[i][m] = getSum(i, m);
            }
        }

        // 불가능상태 설정
        int[][][] dp = new int[N][1<<M][K+1];
        for(int i = 0; i<N; i++){
            for(int m = 0; m<(1<<M); m++){
                Arrays.fill(dp[i][m], -1);
            }
        }

        for(int m = 0; m<(1<<M); m++){
            if((m & (m<<1)) == 0){
                int kCnt = Integer.bitCount(m);
                if(kCnt <= K){
                    dp[0][m][kCnt] = cost[0][m];
                }
            }
        }

        for(int i = 1; i<N; i++){
            for(int m = 0; m<(1<<M); m++){
                if((m & (m<<1)) != 0)
                    continue;
                for(int prev = 0; prev < (1<<M); prev++){
                    if((prev & (prev<<1)) != 0)
                        continue;
                    if((m & prev) != 0)
                        continue;
                    for(int k = 0; k<=K; k++){
                        if(dp[i-1][prev][k] == -1)
                            continue;
                        int nk = Integer.bitCount(m) + k;
                        if(nk > K)
                            continue;
                        dp[i][m][nk] = Math.max(dp[i][m][nk], dp[i-1][prev][k] + cost[i][m]);
                    }
                }
            }
        }

        int ans = 0;
        for(int m=0;m<(1<<M);m++){
            for(int k=0;k<=K;k++){
                ans = Math.max(ans, dp[N-1][m][k]);
            }
        }
        System.out.print(ans);
    }
}

문제 원문

n×m 크기의 격자 정보가 주어집니다. 각 칸에는 하나의 정수 값이 적혀있습니다. 최대 k개의 칸을 선택할 수 있는 조건 하에 선택된 칸에 적혀있는 수들의 합이 최대가 되도록 선택하되 상하좌우로 인접한 칸이 동시에 선택되지는 않도록 하는 프로그램을 작성해보세요.

 

사고의 흐름 및 풀이

N<= 10, M<=10 이라서 그냥 생긴대로 비트마스크 설정해주면 되고 전체 고른 갯수가 K개 조건이 있어서 상태를 하나 더 추가함

dp[N][1<<M][K+1] = N번째 행까지 체크했고 현재 행의 상태가 mask이고 누적 선택 갯수가 k 일때 최대 합

cost[행][마스크] 2차원 배열을 미리 만들어서

나중에 getSum을 중복해서 호출하는 대신 미리 valid 한 마스크에 대해서만 계산함

-> 사실 DP 전이할때 m & (m<<1) == 0인것만 전이해서 거르기때문에 안해도 되긴 하는데 중복 호출을 더 줄여주니까 일단함

 

DP 전이

i = [1, N-1] 일때 모든 현재 마스크와 prev 마스크에 대해서 순회하는데 모든 가능한 k값에 대해서 전이함

현재 마스크는 m & (m<<1) == 0 인것만,

prev도 똑같이 거르고 prev에서 추가로 m & prev == 0인 것만 (위로 안겹치는거) 전이

 

k는 i-1행까지 봤을때의 누적된 선택 수인데 미리 초기화할때 전체를 invalid한 값으로 초기화해놓고 가능한 것만 

0번째 줄에 대해서 초기값을 미리 계산해둔 cost 값으로 초기화시켜놔서 

dp[i-1][prev][k] == -1이면 이전 행의 prev 상태로는 도달할 수 없는 k개의 선택 수이므로 이것도 걸러냄

 

원래는 순회 안에서 N-1일때 최댓값 갱신하는 식으로 했었는데 N이 1일때 갱신하지 않는 문제가 있어서

따로 dp 갱신 다 하고 m = [0, (1<<M)-1], k = [0, K] 일때 dp[N-1][m][k]로 최대값으로 갱신해서 출력함.

---