백준 <Fruit Feast>

백준 알고리즘 11964번

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

11964번: Fruit Feast

---

11964번

Bessie는 쌓여있는 레몬과 오렌지를 발견했다. 이 레몬과 오렌지를 최대한 많이 먹고 싶다!!

Bessie는 최대 T만큼의 포만감을 가질 수 있고, 오렌지를 먹으면 A만큼의 포만감이 차고 레몬을 먹으면 B만큼의 포만감이 찬다. 그리고 물을 한 번 먹을 수 있는데 물을 먹으면 Bessie의 포만감이 반으로 줄어든다. (포만감에 대해 내림을 진행한다.)

Bessie가 최대로 가질 수 있는 포만감을 구하여라.

 

입력으로 첫 줄에 T A B 가 순서대로 들어온다.

 

출력으로는 Bessie가 가질 수 있는 최대 포만감을 구해서 출력하면 된다.

---

문제 해결

BFS를 활용해 문제를 해결했다.

A와 B를 처음 시작으로 설정하고 BFS를 진행하면 된다.

상하좌우로 인접 칸을 가는 전형적인 문제와 다르게 큐에서 꺼낸 값에 A와 B를 각각 더해 나가면서 인접 숫자를 만들어나간다. 또한 물은 1번만 먹을 수 있고 물을 먹으면 포만감이 반으로 줄기 때문에 큐에 넣을 때 만들어진 숫자와 물을 먹었는지 여부를 함께 넣어주었고 방문체크를 진행할 때도 2차원 boolean 배열을 통해 물을 먹었을 때와 물을 먹지 않았을 때를 구분하여 진행했다.

 

bfs(int[] num)

• num은 A와 B로 이루어진 배열이다.
• 먼저 큐와 방문체크 배열 visit을 선언한다. 
  (visit[t][0] 은 t 숫자를 만드는데 물을 먹지 않았음을, visit[t][1]은 t 숫자를 만드는데 물을 먹었음을 의미한다.)
• num 배열을 돌며 큐에 넣고 방문체크를 진행한다. 이때, 물을 먹지 않고 만들 수 있는 숫자 이기 때문에 visit[n][0]에 방문 체크를 진행한다.
• 큐가 빌 때까지 다음과 같은 로직을 반복한다.
  • 큐에서 값을 꺼낸다. -> poll (poll[0]은 가능한 포만감을 의미하며 poll[1]은 물을 먹었는지 여부를 의미한다.)
  • num 배열을 돌며 poll[0]의 값과 덧셈을 진행한다.
    • 만약 그 값이 T보다 크거나, visit[그 값][poll[0]]이 true라면 넘어간다.
    • 그렇지 않다면 큐에 넣고 방문체크를 진행한다.
  • 만약 poll[1]의 값이 0이라면 아직 물을 마시지 않은 것이기 때문에 물을 마신다.
    • 물을 마셨기 때문에 포만감이 반이 되고, visit[현재 포만감의 반][1]을 이용해 방문했는지 확인한다.
    • 방문하지 않았다면 큐에 넣고 방문체크를 진행한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class BOJ_11964 {
    static int T, A, B;
    static boolean[] possible;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        T = Integer.parseInt(inArr[0]);
        A = Integer.parseInt(inArr[1]);
        B = Integer.parseInt(inArr[2]);
        int answer = 0;
        if (T % A == 0 || T % B == 0 || T % (A + B) == 0) {
            answer = T;
        } else {
            answer = bfs(new int[]{A, B});
        }
        System.out.println(answer);
    }

    static int bfs(int[] num) {
        Queue<int[]> Q = new ArrayDeque<>();
        // visit[t][0] : t 포만감을 만드는데 물을 안마셨다
        // visit[t][1] : t 포만감을 만드는데 물을 마셨다
        boolean[][] visit = new boolean[T + 1][2];
        // 포만감 0은 항상 가능
        visit[0][0] = true;
        visit[0][1] = true;
        for (int n : num) {
            Q.add(new int[]{n, 0});
            visit[n][0] = true;
        }
        while (!Q.isEmpty()) {
            int[] poll = Q.poll();
            for (int n : num) {     // Q에서 꺼낸 포만감에 A를 더해보고 B도 더해본다.
                int temp = poll[0] + n;
                if (temp > T || visit[temp][poll[1]]) continue;
                Q.add(new int[]{temp, poll[1]});
                visit[temp][poll[1]] = true;
            }
            // 만약 물을 안마셨으면 물을 마셔본다.
            if (poll[1] == 0) {
                int temp = (int) Math.floor(poll[0] / 2.0);
                if (visit[temp][1]) continue;
                Q.add(new int[]{temp, 1});
                visit[temp][1] = true;
            }
        }
        return check(visit);
    }

    static int check(boolean[][] visit) {
        for (int t = T; t >= 0; t--) {
            if (visit[t][0] || visit[t][1]) return t;
        }
        return 0;
    }
}

---

결과

 

---