[백준] 4811 알약 💊 (Java)

문제 링크

https://www.acmicpc.net/problem/4811

문제 설명

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.
첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

구조화

처음엔 백트래킹으로 접근해봤다.

먹는 방법 두가지를 재귀로 들어가서 w, h가 둘다 '0'이면 방법의 수++

이렇게 할 경우 모든 과정을 다 해봐야됨 -> 시간 초과

import java.io.*;
import java.util.*;

public class Main {
    public static int cnt, n;
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        while (n != 0) {
            cnt = 0;
            recur(n, 0);
            sb.append(cnt).append("\n");

            n = Integer.parseInt(br.readLine());
        }

        System.out.println(sb);
    }

    public static void recur(int w, int h) {
        if (w==0 && h==0) {
            cnt++;
            return;
        }

        if (w-1>=0)
            recur(w-1, h+1);
        if (h-1>=0)
            recur(w, h-1);
    }
}

그래서! 두가리 최적화를 함 -> DP TopDown

1. 함수에서 값 리턴 -> 변수를 안써도 됨

2. dp배열에 저장 -> dp배열에 이미 있는 값은 바로 리턴해서 반복을 줄임

오답 노트

dp배열의 크기를 [31][62]로 했는데, 이는 [w][h]를 뜻함

근데 h가 반쪽이라 31*2로 했는데 31로 해도 됨

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    public static int n;
    public static long[][] dp;
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dp = new long[31][62];
        n = Integer.parseInt(br.readLine());
        
        while (n != 0) {
            sb.append(recur(n, 0)).append("\n");
            n = Integer.parseInt(br.readLine());
        }

        System.out.println(sb);
    }

    public static long recur(int w, int h) {
        if (dp[w][h] != 0){
            return dp[w][h];
        }

        if (w==0 && h==0) {
            return 1;
        }

        if (w-1>=0) {
            dp[w][h] += recur(w - 1, h + 1);
        }
        if (h-1>=0) {
            dp[w][h] += recur(w, h - 1);
        }

        return dp[w][h];
    }
}