백준 14391 종이조각

문제

종이를 잘잘 잘라서 가장 큰 값이 되도록 합시다.

풀이

아직도 백트래킹을 잘 못하는구나를 느끼면서 풀이에 실패하여 답을 보았다.

1. Bitmask

한 변의 길이가 1로 제한된다는 점을 이용하여 각 셀의 상태를 가로 또는 세로로 표시할 수 있다. 이를 이용하면 총 상태의 개수는 $2^{N*M}$ 이다.

2. BackTracking

내가 시도하려던 방법이 실패했던 이유를 나도 모르지만 다른 사람의 코드를 본 결과…