알약

작성일 | 분류 , |
문제는 간단합니다. 분류도 재귀호출입니다.

문제는 간단합니다. 분류도 재귀호출입니다.

무조건 처음에는 1알을 2등분하고 반알을 먹어야 합니다. 그후 온전한 2알과 반알 중 선택해야 합니다.

온전한 알약이 다 소진되면 경우의 수가 발생한다. 아래 그림에 밑줄을 확인해보면 알 수 있습니다.

그리고 중간에 중복이 발생되는 것도 발견 할 수 있습니다.

중복은 메모리에 저장해서 반복적으로 재귀가 수행되지 않도록 하면 됩니다.

문제 설명

  • 당신에게 N개의 알약이 있습니다.
  • 각 알약은 반쪽짜리 알약(H) 두 개로 나뉩니다.
  • 매일 당신은 아래와 같은 두 가지 행동 중 하나를 할 수 있습니다:
    1. 반쪽짜리 알약(H)을 먹는다.
    2. 반쪽짜리 알약(H) 두 개를 합쳐서 한 알짜리 알약(W)으로 만들고 이를 먹는다.

매일 H나 W를 먹으면서 N개의 알짜리 알약이 모두 없어질 때까지 이 과정을 반복할 때, 모든 과정을 출력할 수 있는 순열의 경우의 수를 구하는 문제입니다.

예제

  • N = 1일 때:
  • 가능한 순열: W
  • N = 2일 때:
  • 가능한 순열: WHW, WW

문제 풀이

문제의 해결 방법은 다이나믹 프로그래밍(DP)을 사용하는 것입니다. 이를 위해 두 가지 상태를 고려합니다:

  1. 현재 남아 있는 반쪽짜리 알약(H)의 수.
  2. 현재 남아 있는 알짜리 알약(W)의 수.

우리는 재귀적 접근을 통해 모든 가능한 순열을 탐색할 수 있습니다. 다만 중복되는 계산을 피하기 위해 메모이제이션을 사용할 수 있습니다.

접근 방법

  1. 초기 상태: * H = N, W = 0으로 시작합니다. * 즉, 모든 알약이 반쪽짜리로만 존재합니다.
  2. 재귀 함수 정의: * dp(H, W)는 남아 있는 반쪽짜리 알약이 H개, 알짜리 알약이 W개일 때 가능한 순열의 수를 의미합니다.
  3. 점화식: * 만약 H > 0이라면, H를 하나 줄이고 dp(H-1, W+1)을 호출합니다. * 만약 W > 0이라면, W를 하나 줄이고 dp(H, W-1)을 호출합니다.
  4. 기저 조건: * H == 0이고 W == 0이면 가능한 순열의 수는 1입니다.

이제 이 접근을 구현한 코드를 살펴보겠습니다.


import java.util.Scanner;

/**
 * 제목 : 알약
 * 링크 : https://www.acmicpc.net/problem/4811
 * 분류 : 재귀 호출
 */
public class Main {

	static long[][] dp = new long[31][31];

	public static void main(String[] args) {
		var sc = new Scanner(System.in);
		var sb = new StringBuilder();
		while (true) {
			var n = sc.nextInt();
			if (n == 0) break;
			recursive(n, 0);
			sb.append(dp[n][0] + "\n");
		}
		System.out.println(sb.toString());
	}

	private static long recursive(int w, int h) {
		if (dp[w][h] > 0) return dp[w][h];
		if (w == 0) return 1;
		dp[w][h] = recursive(w - 1, h + 1);
		if (h > 0) dp[w][h] += recursive(w, h - 1);
		return dp[w][h];
	}
}