[BOJ 23816] 백준 23816번 - 옷걸이걸이걸이
1. 문제
$23816$. 옷걸이걸이걸이 (2021 POSTECH Programming Open Contest D번)
2. 풀이
현재 상태가 이전의 어떤 여러 상태에서 파생된 결과이기 때문에 dp를 사용한다.
$dp[i][j] \rightarrow$ 옷걸이를 걸 수 있는 위치 $i$개를 사용하여 옷걸이 $j$개를 건 경우
현재 상태(dp[i][j])를 만들기 위해서는 옷걸이를 걸 수 있는 위치 i-1개를 사용한 상태(dp[i-1][?])에서 새로운 옷걸이 거는 위치에 옷걸이를 $0, 1, 3, 7, 15$개(완전 이진 옷걸이) 걸면 된다.
옷걸이를 $0, 1, 3, 7, 15$개 걸면, 옷을 추가로 $0, 1, 2, 4, 0$개 더 걸 수 있다. ($15$개 완전 이진 옷걸이를 완성하면, 옷걸이는 걸 수 있되 옷은 걸 수 없는 경우이므로 더 걸 수 있는 옷의 수는 $0$개이다.) (코드 33~34줄)
$dp[i][j] = max(dp[i][j-0]+0,$ $ dp[i][j-1]+1,$ $ dp[i][j-3]+2,$ $ dp[i][j-7]+4,$ $ dp[i][j-15]+0) \quad$ (코드 37줄)
$1\leq N\leq 5000,$ $ 1\leq M\leq 10000$이므로 $N\times M=50,000,000$ 이어서 시간 내에 충분히 이중for문을 돌릴 수 있다. 앞뒤로 왔다갔다 하는 것도 아니라 계속 $i$가 증가하는 방향으로 나아가므로 for문 dp가 가능하다.
재귀함수로 그냥 구현하면 TLE가 발생하기 때문에, 다음과 같은 방법들이 필요하다.
- $m==0$ 인 경우, 옷걸이를 전부 사용하고 나머지 남은 $n$에 대해서는 어차피 $0$개씩 배정하는 것이 확정이므로 바로 $0$을
return(코드 19~21줄) - $m\leq n$ 인 경우, $m$개의 위치에 $m$개의 옷걸이를 각각 한 개씩 거는 것이 옷을 최대($m$개)로 걸 수 있다는 것이 확정이므로 바로 $m$을
return(코드 25~27줄) - $1$번이 결국 옷걸이를 $0$개 걸어서 옷을 $0$개 더 추가하는 것과 같고, $2$번이 결국 옷걸이를 $1$개 걸어서 옷을 $1$개 더 추가하는 것과 같으므로, 해당 케이스를 제외한다. (코드 33~34줄에서
(hanger, dress) = (0,0), (1,1)을 제외) (행동의 순서가 바뀌어도 상관없으므로 가능함)
3. 채점 결과
4. 회고
dp문제를 만나면 for문으로 처리할지 재귀함수로 처리할지 항상 고민이다. 나는 재귀함수로 풀었지만, 이 문제는 for문으로 푸는 것이 더 쉽다.
해당 문제에서 dp를 재귀함수로 구현하게 되면 for문보다 훨씬 많은 시간이 걸리는 것인지에 대해서 확실하게 정의를 내리지 못하겠다.
굳이 예외케이스를 신경쓰지 않더라도 시간초과가 나지 않을 줄 알았다. 그런데 시간초과가 나서 최대한 시간을 줄이고자 위와 같은 방법들을 생각해내서 도입했다.
댓글남기기