[백준/python] 14391번 종이조각

1. 문제

 

이 문제는 직사각형 종이를 한 변이 1인 직사각형 모양의 조각으로 잘라서

조각 안의 수를 왼->오, 위->아래로 붙인 수의 합을 최대로 만드는 프로그램을 짜는 문제이다.

특이점은 종이의 크기가 최대 4*4로 작다는 점이다.

2. 풀이

이 문제는 다양한 시도를 했으나 그만큼 실패를 많이 경험했다.

처음에는 단순히 생각해서 그냥 가로로 쭉 자른 종이들의 합, 세로로 쭉 자른 종이들의 합,

이 두 값을 비교해서 큰 값으로 하면 되잖아? 라고 생각했다.

왜냐면 종이를 쭉 이어서 자르지 않고 막 조각내면 자릿수가 작아지니까.

근데 이건 잘못된 생각이었다.

문제에서 나온 예시와 달리 '0'이 들어가는 경우에 이상한 상황이 생긴다.

 

예를 들어서, 아래와 같은 종이조각 말이다.

0	0	2	3
0	0	1	2
9	9	9	9
0	0	1	1

 

1. 가로로 쭉 자르면 23 + 12 + 9999 + 11이다.

2. 세로로 쭉 자르면 90 + 90 + 2191 + 3291이다.

그렇다고 답이 둘 중에 있냐고 묻는다면 그건 아니다.

답은 아래 두 줄은 9999, 11로 자르고 나머지 숫자는 23과 12 대신

세로로 21과 32로 해야 최댓값이 되는 것이다.

0이 나오는 경우에 문제가 생김을 확인하고 다른 로직을 짰다.

 

숫자가 작아서 그리디로 단순구현을 했지만 계속 문제가 해결되지 않았다.

이 뒤에는 테스트케이스는 통과하길래 도대체 어디서 틀린 건지 알 수가 없어서 검색창의 도움을 받았다.

 

그리고 비트마스킹이라는 개념을 처음 접했다.

코딩테스트 스터디를 진행하며 다른 분의 발표를 듣고 비트마스킹의 유용함을 제대로 알게 되었고

이 알고리즘을 학습해서 문제를 해결했다.

 

아래 글은 알고리즘을 정리한 글이다.

https://jemarque.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9

[알고리즘] 비트마스킹

 

그래서 내가 풀이한 방식은 비트마스크를 사용해 모든 경우의 수를 따져보고

이를 비교해서 그 중 최댓값을 찾아내는 방식이다.

비트마스크를 사용하기 위해 최대 4 * 4 배열을 한 줄로 만든다.

각각의 인덱스에 대해서 비트 연산을 사용해 집합에 원소 포함 여부를 확인하고,

원소가 1일 때와 0일 때 다른 처리를 해준다.

반복문을 쭉 돌린 후 모든 경우의 수에 대한 확인이 끝나면 최댓값을 출력한다.

3. 코드

def rip_paper():
    answer = 0
    # 비트마스크로 경우의 수 모두 따져보기
    for bitmask in range(1 << (n * m)):
        total = 0
        # 가로 합
        for i in range(n):
            sum1 = 0
            for j in range(m):
                idx = i * m + j
                if bitmask & (1 << idx) != 0: # 가로일 때
                    sum1 = sum1 * 10 + paper[i][j]
                else: # 세로일 때 초기화
                    total += sum1
                    sum1 = 0
            total += sum1
        
        # 세로 합
        for j in range(m):
            sum2 = 0
            for i in range(n):
                idx = i * m + j
                if bitmask & (1 << idx) == 0: # 세로일 때
                    sum2 = sum2 * 10 + paper[i][j]
                else: # 가로일 때 초기화
                    total += sum2
                    sum2 = 0
            total += sum2
        answer = max(answer, total)
    return answer
    
n, m = map(int, input().split())
paper = [list(map(int, input())) for _ in range(n)]
print(rip_paper())

4. 결과

 

비트마스킹이라는 새로운 알고리즘을 배웠다.

dp 대신에 쓸 일이 생길 것 같다!