[백준][14391번][DPS] 종이 조각

스도쿠

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

<문제>

<코드>

#include <iostream>
#include <cstdlib>
#include <stdio.h>
 
using namespace std;
 
int arr[4][4];
 
 
int main()
{
    int n,m;
    int t,i,j,cur;
    int ans = 0;
    cin >> n >> m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%1d",&arr[i][j]);
 
    // 비트마스킹 기법
    for(t=0; t < ((1<<n*m)); t++)
    {
        int sum = 0;
        // 가로 일 때
        for(i=0;i<n;i++)
        {
            int psum = 0;
            for(j=0;j<m;j++)
            {
                cur = m * i + j;
                // 계속 가로면 자리 수 업!
                if((t & (1<<cur)) == 0)
                {
                    psum = 10 * psum + arr[i][j];
                }
                // 세로면 끝내고 더해주자
                else
                {
                    sum += psum;
                    psum = 0;
                }
            }
            // 마지막에 가로로 끝내면 안더해주니깐 sum에 추가해주기
            sum += psum;
        }
        // 세로 일 때는 i와 j만 바꿔주기 (검사하는 순서만 바꿔여)
        for(j=0;j<m;j++)
        {
            int psum = 0;
            for(i=0;i<n;i++)
            {
                cur = m * i + j;
                // 계속 가로면 자리 수 업!
                if((t & (1<<cur)) != 0)
                {
                    psum = 10 * psum + arr[i][j];
                }
                // 세로면 끝내고 더해주자
                else
                {
                    sum += psum;
                    psum = 0;
                }
            }
            // 마지막에 가로로 끝내면 안더해주니깐 sum에 추가해주기
            sum += psum;
        }
        if(ans<sum)
            ans = sum;
    }
    cout << ans;
}
 

<문제 푼 요령>

1. 모든 경우의 수에서 각각의 칸은 가로 또는 세로의 칸으로 나뉠 수 있다는 점에 주목한다. 최대 칸의 수가 16개이므로 비트마스킹 기법으로 풀 수 있다.

2. 비트마스킹으로 풀 경우 최대 경우의 수는 2^16 * 16이므로 1억을 넘지 않는다. 처음에 가로의 경우를 조사해주고 그 다음에 세로의 경우를 조사해준다.

3. 유의할 점은 cur 값이 가로에서나 세로에서나 같은 값으로 설정되어야 한다. 왜냐하면 모든 칸들의 인덱스를 고유하게 놓고 검사하는거기 때문에 가로에서와 세로에서와 검사하는 값이 겹치면 안된다.