오랜만에 풀어보는 Backtracking 태그의 문제이다. 예전에 군대 있을때만 해도 한참 이 주제에 깊게 빠져들어서 백트래킹 문제들만 풀었는데 요즘들어 Greedy, Sorting, DP, 시뮬레이션 등등 다양한 문제들에 눈이 더 가게 되는거같다.
문제는 matchsticks 라는 벡터가 주어졌을때 각 초가 길이를 의미하는데 이 초들을 "전부" 써가지고 사각형을 만들수 있다면 true를 리턴하고 그렇지 못한다면 false를 리턴하면 되는 문제이다. 이 문제는 Backtracking 보다는 DP에 좀 더 가까운 문제지만 모든 테스트케이스가 Brute Force로 풀어진것도 신기했었다.
이런 유형의 문제를 오랜만에 풀다보니 index를 조절하는 과정에서 좀 문제가 있었고 dfs 자체를 void 로 리턴 할려다보니 처음에는 많은 어려움이 있었다.
처음에 이렇게 풀어보고 70프로 이상의 테스트케이스가 맞았는데 결국은 실패했다. 그리고 내가 치명적이게 실수를 한 생각이 있었는데 사각형 한 변의 길이를 벡터안에 가장 큰 숫자로 할려던게 많이 어긋났었다. 사각형이 만들어질수있는 벡터에 경우에는 그 안에 있는 모든 숫자를 더하고 4로 % 했을때 0으로 나뉘어 떨어져야지만 가능한것이었는데 이 부분을 놓쳤었다.
그리고 추가적으로 void 로 리턴을 할려고 하니깐 중간부터 이상한 부분을 느끼긴 했었다.
다시 고친 내 코드. Combination 느낌으로 index를 임의에 index를 넣어준다음에 만약에 한번도 안써본 stick 이라면 curr_stick 에 추가를 해주었고 재귀 과정을 계속 따라갔다. 그 결과, curr_stick 이 사각형의 변에 맞는 순간 다시 재귀를 해줬어야 했는데 아마 이런 부분에서 DP 가 필요한게 아닐까 싶다. 그리고 내가 실수했던것중 하나는 다시 재귀를 할때 index를 0으로 설정 안하고 그 자리에서 다시 할려고 하니 문제가 나올수밖에 없었다. 좀 Combination Sum 과 비슷한 문제일수도 있지만 조금 더 창의적인 생각이 필요했던 그런 문제였던거 같아서 어렵게 느껴졌었다.
배운점:
1. Backtracking 아직 많이 부족하니깐 내가 풀었던것들을 복습하면서 다시 배워보자
2. 항상 Basecase를 잘생각해보자
