BOJ 4348 막대 정사각형

길이가 다양한 N개의 막대가 주어지고, 그 막대들을 모두 이용해서 정사각형을 만들 수 있는지 없는지를 구하는 문제이다.

정사각형은 네 변의 길이가 같기 때문에 주어진 막대들의 합을 4로 나눈 값이 정사각형의 한 변의 길이가 될 것이다. (주어진 막대들이 합이 홀수이면 no출력)

한 변의 길이 len을 구하게 되면 이제 주어진 막대들을 한 번씩 이용해서 len을 4개 만들 수 있는지 따져봐야 한다. 이제 이 부분에서 매우 많은 경우가 나오고 겹치기 때문에 dp(memoization)로 처리해주는데, 비트마스크를 활용해서 어떤 막대기를 사용했는지 상태를 표시해준다. 막대기의 개수가 최대 20개이므로 상태를 비트로 표현할 수 있다.
d[state]=현재 상태 state에서 시작할 때, 정사각형을 만들 수 있는지 없는지.
d[state]=(d[nextState1] || d[nextState2] || ...); 하나라도 true이면 true, 모두 false이면 false.

직접 구현을 해보면서 생각해 봐야겠다.
일단 구현해서 제출했는데 AC를 받았다! 내 풀이를 적어보겠다.
d[state]=현재 상태 state에서 시작할 때, 정사각형을 만들 수 있는지 없는지인데, dp를 구현하는 재귀함수에 parameter로 state와 한 변의 남은 길이, 만들어야할 변의 개수 를 보냈다.(정사각형 한 변의 길이는 전역변수로 처리) 정사각형에는 총 4개의 변이 있고, 한 변씩 만들어 갈 것인데 state를 보고 아직 선택하지 않은 막대기를 골라서 정사각형의 변을 하나씩 만들어 가는 식이다. 처음에는 한 변의 남은 길이로 정사각형의 변의 길이가 들어올 것이고, 그럼 아직 선택되지 않은 막대기 중 그 길이보다 짧은, 혹은 같은 막대기를 선택해서 state에 선택했다고 표시해주고, 한 변의 남은 길이(정사각형의 변의 길이)에서 선택한 막대기의 길이를 빼서 다음 함수의 "한 변의 남은 길이"로 보내준다. 이렇게 해서 한 변이 다 만들어지면 그 때, 또 하나의 parameter인 만들어야할 변의 개수를 -1 해준다.

그러니까 처음에는 dp(state : 0, remained : len, num : 4) 이렇게 시작한다.
그래서 기저 조건으로는 num이 0이되면 정사각형이 완성된 것이므로 return 1을 해준다.
정사각형을 완성 못했는데 더이상 선택할 것이 없는 경우는 자동으로 return 0이 된다.

그리고 계산을 위해 paramter로 여러 개를 보내줬지만 d[state]하나로 memoization이 가능한 것은 어떤 변을 선택했냐에 따라서 만들 수 있는 변의 개수나 남은 길이는 다 똑같이 정해지기 때문이다!