P2629

[baekjoon-2629] 양팔저울

풀이 과정

시간 제한, 메모리 제한을 따졌을 때 DP로 풀어야 한다. (처음에 조합으로 모든 경우의 수를 Set에 넣고 계산했다가 메모리 초과가 발생하였다.)

그럼 한 시점에서 따질 수 있는 경우의 수는 다음의 세 가지이며, 이 때의 시점은 현재 몇 번째 추까지 계산했는지이다.

현 시점 : i번째 추를 계산 중
1. i번째 추를 사용하지 않음
2. i번째 추를 구슬 반대쪽에 올림
3. i번째 추를 구슬쪽에 올림

위 경우의 수에 대하여 메모이제이션을 해나가면서 재귀를 돌린다. 시간초과가 발생하지 않도록 종료조건 및 방문 여부를 신경써줘야 하는데, 현 시점에서 추를 사용했거나 / 안 사용했거나에 따라 방문 여부의 차원이 달라지므로 방문 배열을 2차원 배열로 선언해야 한다.