[BOJ] (BIT, BF)14391번 종이 조각 ★★

 

 

일단 배열을 어떻게 저렇게 가로 세로로 칸을 나누는지 감을 못잡았다

2차원 배열을 1차원 배열로 풀어서, 각 요소마다 인덱스를 부여.

가로방향을 1, 세로방향을 0이라고 생각하면, 총 경우의 수는 2의n*m제곱.

1과0으로 표현할 거니까 비트마스킹을 이용하여 저장.

 

인덱스 k = i*m + j이고, 이 k번째 요소가 0인지 1인지 확인하려면 b&(1<<k) == 0 이용

now = now*10 + arr[i][j] 을 이용해서 수 합치기

 

n, m = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(list(map(int, list(input()))))

ans = 0
for b in range(1<<m*n):
    _sum = 0
    # 가로 0  세로 1
    
    #가로방향
    for i in range(n):
        now = 0
        for j in range(m):
            k = i*m + j
            
            if b&(1<<k) == 0:
                now = now*10 + arr[i][j]
            else:
                _sum += now
                now = 0
                
        _sum += now
    
    # 세로 방향
    for j in range(m):
        now = 0
        for i in range(n):
            k = i*m + j
            
            if b&(1<<k) != 0:
                now = now*10 + arr[i][j]
            else:
                _sum += now
                now = 0
            
        _sum += now
        
    ans = max(ans, _sum)
    
    
print(ans)

 

 

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

14391번: 종이 조각