[백준]#11964 Fruit Feast

문제

Bessie has broken into Farmer John's house again! She has discovered a pile of lemons and a pile of oranges in the kitchen (effectively an unlimited number of each), and she is determined to eat as much as possible.

Bessie has a maximum fullness of T (1 <= T <= 5,000,000). Eating an orange increases her fullness by A, and eating a lemon increases her fullness by B (1 <= A,B <= T). Additionally, if she wants, Bessie can drink water at most one time, which will instantly decrease her fullness by half (and will round down).

Help Bessie determine the maximum fullness she can achieve!

입력

The first (and only) line has three integers T, A, and B.

출력

A single integer, representing the maximum fullness Bessie can achieve.

예제 입력 1

8 5 6

예제 출력 1

8

풀이

이 문제는 dp(다이나믹 프로그래밍) 알고리즘을 이용해서 풀 수 있었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int max = 0;
    static boolean[] dp;        //지나온 fullness 체크를 위한 배열

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int T = Integer.parseInt(input[0]);
        int A = Integer.parseInt(input[1]);
        int B = Integer.parseInt(input[2]);

        dp = new boolean[T+1];
        dfs(0, T, A, B, false);

        System.out.println(max);
    }

    public static void dfs(int temp, int T, int A, int B, boolean flag) {
        if(dp[temp]) return;              //지나온 fullness면 중지

        max = Math.max(max, temp);
        dp[temp] = true;

        int sum = temp+A;

        if(sum<=T) {
            if(!flag)
                dfs(sum/2, T, A, B, true);

            dfs(sum, T, A, B, flag);
        }

        sum = temp+B;

        if(sum<=T) {
            if(!flag)
                dfs(sum/2, T, A, B, true);

            dfs(sum, T, A, B, flag);
        }
    }
}