나는 항상 보면 접근 자체를 복잡하게 생각하는 경우가 많다. 부족한 두뇌로 복잡한 계산을 생각하다보니 스스로 지쳐서 머리 회전이 멈추는 듯 하다. 재귀는 항상 기억할 것은, 상태공간트리를 그려가며 작은 sub-problem으로부터 base case를 먼저 생각하고 그 후 recursion case를 정해 나가는 것이다. 이 과정만 제대로 할줄 안다면 정말 완벽할텐데..
어쨌든 문제는 다음과 같다.
70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.
첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이 때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?
https://www.acmicpc.net/problem/4811
나의 고질적인 문제 중 하나인 난독증은 정말 많은 시간을 헛되이 쓰게 하는것 같다. 제발 문제좀 똑바로 읽자... 어쨌든 이 문제에서 중요한 것은 첫째 날은 반드시 반을 쪼개어 약을 먹는 다는 것이고, 또 반을 쪼개 먹기 때문에 최대 소요되는 날짜는 2N이라는 것이다. 처음에는 N자체를 base case로 수렴하기 위한 parameter로 여기는 바람에 많은 고생을 했다. 하지만 상태공간트리로 삽질을 계속 한 결과 중요한 것은 N으로 부터 파생되는 W과 H(여기서는 W를 병 속에 남은 온전한 알약, H를 반으로 쪼개어진 알약의 갯수)라는 것을 알게 되었다.
위의 트리는 N=2인 경우의 상태공간트리이다. 처음 약을 먹지 않은 상태에는 W=2, H=0인 상태 일 것이다. 이 때 첫째 날은 약을 쪼개서 하나는 먹고 하나는 다시 넣어두니 W=1, H=1일 것이다. 이 상태에서 가능한 모든 경우의 수는 온전한 알약을 쪼개어 먹는 경우의 수와 아니면 반으로 쪼개진 알약을 골라 먹는 경우의 수의 합이다. 이는 모든 sub-problem에 적용할 수 있는 recursive case로 보면 된다. base case는 W=0인 경우, 선택지는 모든 쪼개진 알약만을 먹는 방법인 경우인 w=0인 경우로 보면 된다.
base case:
f(w,h) = 1 if w==0
recursive case:
f(w,h) = f(w-1,h+1) if w>0 && h<1
f(w,h) = f(w-1, h+1) + f(w, h-1) otherwise
그리고 중복 계산을 방지하기 위해 memorization 방식으로 값을 저장 한후 사용하였다.
Source code
'programming > algorithm' 카테고리의 다른 글
[boj-1504]특정한 최단경로 (0) | 2017.07.31 |
---|---|
[graph]위상정렬 (0) | 2017.07.25 |
[graph] BFS,DFS (0) | 2017.07.23 |
(Recursion) 미로 찾기 (0) | 2017.07.09 |
Recursive(재귀 함수) (0) | 2017.07.08 |