[알고리즘] 백준 14391 종이조각 // 비트마스킹, 1차원을 2차원으로 바꾸는힘

* 요약

• 차원을 2차원으로 바꾸는힘
  • i*m + j 암기!!!!

i*m + j 공식이 어떻게 2차원 배열을 1차원으로 변환하는지 설명

예를 들어 2x3 배열이 있다고 해보죠:

1 2 3
4 5 6

이 공식이 작동하는 방식을 단계별로 설명하겠습니다:

1. 각 행(i)마다 건너뛰어야 하는 개수:
   • 첫 번째 행(i=0): 0개 건너뜀 (0*m)
   • 두 번째 행(i=1): m개 건너뜀 (1*m)
   • 세 번째 행(i=2): 2m개 건너뜀 (2*m)
2. 열 위치(j)를 더하기:
   • j=0: 첫 번째 열
   • j=1: 두 번째 열
   • j=2: 세 번째 열
3. 예시로 (1,2) 위치의 경우:
   • i=1, j=2, m=3일 때
   • 1*3 + 2 = 5
   • 즉, 1차원 배열에서 5번 위치가 됨

이렇게 변환하는 이유:

1. 비트마스크는 1차원으로만 동작
2. 2차원 위치를 1차원으로 고유하게 매핑해야 함
3. 각 위치가 겹치지 않고 순서대로 매핑되어야 함

실제 사용 예:

if(subset & (1<<(i*m+j))) {
    // i행 j열 위치가 1인지 확인
}

이 공식은 2차원 배열을 행 우선(row-major) 순서로 1차원으로 펼치는 표준적인 방법입니다.

• 비트로 가로, 세로를 표현하는것이 조금 발상적.

 

* 숫자 배열의 가로/세로 합 최대화 알고리즘

문제 설명

N x M 크기의 숫자 배열이 주어졌을 때, 각 행은 가로로 읽거나 세로로 읽어서 만들 수 있는 합의 최대값을 구하는 문제입니다.

입력 예시

1 2 3
4 5 6

핵심 아이디어: 비트마스크를 이용한 상태 표현

1. 비트마스크 표현 방식

• 각 위치를 0 또는 1로 표현하여 해당 위치를 가로로 읽을지(1) 세로로 읽을지(0) 결정합니다.
• N x M 배열의 경우 총 N*M 비트가 필요합니다.

예시: 2x3 배열의 경우

위치 인덱스:    비트 위치:
0 1 2           5 4 3
3 4 5           2 1 0

2. 비트마스크 해석 방법

• 110001(2) 의 경우:
• 1 1 0 // 1: 가로로 읽음 0 0 1 // 0: 세로로 읽음
• 첫 번째 줄의 '11'은 첫 두 숫자를 가로로 연결해서 읽는다는 의미
• '0'은 그 위치의 숫자를 세로로 읽는다는 의미

알고리즘 동작 과정

1. 모든 가능한 조합 생성

int N = n*m;
for(int subset = 0; subset < (1<<N); ++subset) {
    // 각 조합에 대해 계산
}

• 총 2^(N*M)개의 조합이 생성됨
• (1<<N)은 2^N을 의미

2. 가로 합 계산

// 각 행에 대해
for(int i=0; i<n; ++i) {
    int sum = 0;
    for(int j=0; j<m; ++j) {
        // i*m + j: 2차원 배열의 위치를 1차원으로 변환
        if(subset & (1<<(i*m+j))) {
            sum = sum*10 + arr[i][j];  // 가로로 연결된 숫자 생성
        } else {
            garo_sum += sum;  // 이전까지의 합을 더함
            sum = 0;  // 새로운 숫자 시작
        }
    }
    garo_sum += sum;  // 마지막 남은 숫자 더하기
}

3. 세로 합 계산

// 각 열에 대해
for(int j=0; j<m; ++j) {
    int sum = 0;
    for(int i=0; i<n; ++i) {
        if(!(subset & (1<<(j+i*m)))) {  // 비트가 0인 경우
            sum = sum*10 + arr[i][j];
        } else {
            sero_sum += sum;
            sum = 0;
        }
    }
    sero_sum += sum;
}

시간 복잡도 분석

• 총 조합의 수: O(2^(N*M))
• 각 조합별 계산: O(N*M)
• 전체 시간 복잡도: O(2^(N_M) * (N_M))

구현시 주의사항

1. 비트 연산자 우선순위
   • 1<<(i*m+j)에서 괄호 필수
   • 비트 시프트 연산자는 덧셈/뺄셈보다 우선순위가 낮음
2. 숫자 연결 처리
   • sum = sum*10 + arr[i][j]로 연속된 숫자를 하나의 수로 만듦
   • 예: 1, 2, 3을 차례로 연결하면 123이 됨
3. 남은 숫자 처리
   • 각 행/열의 계산이 끝난 후 남은 sum을 반드시 더해줘야 함
   • 마지막 숫자 그룹이 처리되지 않을 수 있음

최적화 팁

1. 입력 크기가 작은 경우에만 사용 가능
2. N, M이 커지면 다른 알고리즘 고려 필요
3. 메모이제이션을 통한 최적화 가능

 

* 최종코드

#include <bits/stdc++.h>
using namespace std;   

int n,m, arr[5][5], ret;

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cin >>n>> m;

   for(int i=0;i<n;++i) {
      string s;
      cin>>s;
      for(int j=0;j<m;++j) {
         arr[i][j]=s[j]-'0';
      }
   }

   int N = n*m;
   for(int subset = 0; subset < (1<<N);++subset) {
      int garo_sum=0;
      for(int i=0;i<n;++i) {
         int sum=0;
         for(int j=0;j<m;++j) {
            /**
             *  m=3
             *  0 1 2 / 0(i) * m + 0(j), 0*m+1, 0*m+2
             *  3 4 5 / 1 * m + 0, ...
             *  6 7 8
             */
            if(subset & (1<<(i*m+j))) { 
               sum = sum*10 + arr[i][j];
            }
            else {
               garo_sum +=sum;
               sum=0;
            }
         }
         garo_sum += sum; // Add remaining sum
      }

      int sero_sum=0;
      for(int j=0;j<m;++j) {
         int sum=0;
         for(int i=0;i<n;++i) {
            if(!(subset & (1<<(j+i*m)))) {
               sum = sum*10 + arr[i][j];
            }
            else {
               sero_sum +=sum;
               sum=0;
            }
         }
         sero_sum += sum; // Add remaining sum
      }
      ret = max(ret, garo_sum + sero_sum);
   }

   cout<<ret;
   
  
   return 0;
}