[boj-4811]알약

나는 항상 보면 접근 자체를 복잡하게 생각하는 경우가 많다. 부족한 두뇌로 복잡한 계산을 생각하다보니 스스로 지쳐서 머리 회전이 멈추는 듯 하다. 재귀는 항상 기억할 것은, 상태공간트리를 그려가며 작은 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

package recursion; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; /** * Created by junhyeok on 2017-07-15. * Problem NO: 4811 */ public class Capsule { public static long[][] map; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n; while ((n = Integer.parseInt(br.readLine())) != 0) { map = new long[2 * n + 1][2 * n + 1]; int w = n - 1; int h = 1; System.out.println(split(w, h)); } } public static long split(int w, int h) { if (w > 0 ) { if (map[w][h] != 0) return map[w][h]; } if (w == 0) { map[w][h] = 1; return 1; } else { long sum = 0; sum += split(w - 1, h + 1); if (h >= 1) sum += split(w, h - 1); map[w][h] = sum; return sum; } } }