[Python/BOJ] 백준 14391 종이조각 _비트마스킹

이 문제는 비트마스킹을 사용해 푼다. 

이해하면 어렵지는 않은데 처음에 이해하기가 까다로웠다.

 

 

 

비트마스킹 관련 포스팅은

https://what-am-i.tistory.com/348

 

 

 

1 : 가로 (우측)

0 : 세로 (아래)

로 생각해서 푼다.

 

종이는 각 칸마다 가로로 자르거나 세로로 자르는 방법만 있으므로 

모든 자리에는 2가지의 상태가 존재한다. 

모든 칸의 개수는 n*m이고 각각 2가지씩 방법이 있으므로 2^(m*n)가지가 존재한다.

이것을 비트마스크로 1<<(m*n)으로 만들 수 있다. 

 

 

모든 판의 경우(1<<(m*n))를 돌면서 가장 큰 종이조각의 합을 구하는 것이다. (일렬로 늘여놓았다고 생각하면 된다.) 

 

---

 

ans = 0

1. 모든 판의 경우를 돈다.

       total = 0

1-1. 가로의 합을 구한다.

1-2. 세로의 합을 구한다.

1-3. 가로의 합 + 세로의  합을 구해 total을 구한 후 ans값과 비교하여 ans보다 크다면 ans에 저장한다. 

 

 

이중 for문으로 모든 칸을 돌면서 해당칸이 (가로 or 세로)가 맞는지 확인하여 맞으면 더하던 곳에 계속 더하고 아니라면 total에 저장해 놓은 뒤 더하던 값을 0으로 초기화한다. 

 

 

---

 

 

코드에 

if i & (1<<idx) != 0 :

가 있는데 이 코드의 의미를 해석해보자.

 

i는 일렬로 늘어진 현재 판을 의미한다. 

이 판때기는 가로로 더할 값은  1으로 세로로 더할 값은 0으로 되어있다. 

idx는 현재 이중 for문을 돌면서 더할 현재 값이다. 

 

이를 &연산을 하면 둘다 1일때만 1이된다. 

1<<idx를 하면 idx자리만 1이되고 나머지는 0이된다.

 

 

이를 i와 &연산을 하면

만약 idx자리가 i에서 0(세로)라면 결과는 0이 될것이고

i에서 1이라면 & 연산결과 둘다 1이므로 0이 아닌수가 될것이다. (자리수를 모르므로 0이 아니라고 생각하면 된다.)

 

 

 

코드 :

 

def bit() :   
    global ans 
    # 종이에서 가로로 더할지 세로로 더할지 경우는 각 자리에서 2가지 
    # 2 ^(n*m) 
    for i in range(1<<n*m) :
        total = 0
        # 가로합 
        for x in range(n) :
            rowsum=0
            # 열을 돌면서 
            for y in range(m) :
            	# 판에서의 번호(idx)를 구함 
                idx = x*m + y
                # 판에서 가로라면 
                if i &(1<<idx) !=0 :
                	# 더해준다. 
                    rowsum = rowsum*10 + mp[x][y] 
                else :
                	# 아니라면 연속되지않은 것이므로 total에 더해준 뒤 0으로 초기화 
                    total += rowsum
                    rowsum = 0
            total += rowsum

        # 세로합 
        for y in range(m) :
            colsum = 0
            # 행을 돌면서 
            for x in range(n) :
            	# 판에서의 번호(idx)를 구함
                idx = x*m + y 
                # 판에서 세로라면 
                if i & (1<<idx) == 0 :
                    colsum = colsum*10 + mp[x][y] 
                else :
                    total += colsum
                    colsum = 0
            total += colsum 
        ans = max(ans,total)
    


if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input()))for i in range(n)]
    
    ans = 0
    bit()
    print(ans)

 

 

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://lagooni.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%A2%85%EC%9D%B4-%EC%A1%B0%EA%B0%81-14391%EB%B2%88-Python-Bitmasking

[백준] 종이 조각 14391번 (Python) -Bitmasking

https://vixxcode.tistory.com/23

14391번 종이조각 백준 파이썬