백준 1679번 숫자놀이 Java

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

문제

---

생각하기

---

• BFS, DP 문제이다.
  • 번호가 낮은 문제인데도 많이 푼 사람이 없음
• 메모리 초과가 발생해서 고생했다.

동작

        for (int i = 0; i < N; i++) {
            que.offer(new Game(arr[i], 1));
            isVisited[arr[i]] = true;
        }

        while (!que.isEmpty()) {
            Game current = que.poll();

            if (current.count < K) {
                for (int next : arr) {
                    if (isVisited[next + current.num]) continue;
                    isVisited[next + current.num] = true;
                    que.offer(new Game(next + current.num, current.count + 1));
                }
            }
        }

카드를 하나만 사용했을 때를 시작으로 해서

count가 K가 될 때 까지 만들어지는 모든 값을 isVisited[]에서 true처리를 하고 결과를 반환하면 된다.

결과

코드

---

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, K, max;
    private static int[] arr;

    private static class Number {
        int num;
        int count;

        private Number(int num, int count) {
            this.num = num;
            this.count = count;
        }
    } // End of Number class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        boolean[] ret = BFS();
        int idx = 1;
        for (; ; ) {
            if (!ret[idx]) break;
            idx++;
        }

        if (idx % 2 == 0) {
            sb.append("holsoon win at ").append(idx);
        } else {
            sb.append("jjaksoon win at ").append(idx);
        }

        return sb.toString();
    } // End of solve()

    private static boolean[] BFS() {
        ArrayDeque<Number> que = new ArrayDeque<>();
        boolean[] isVisited = new boolean[(max * K) + 1];

        for (int i = 0; i < N; i++) {
            que.offer(new Number(arr[i], 1));
            isVisited[arr[i]] = true;
        }

        while (!que.isEmpty()) {
            Number cur = que.poll();

            if (cur.count < K) {
                for (int next : arr) {
                    if (isVisited[next + cur.num]) continue;
                    isVisited[next + cur.num] = true;
                    que.offer(new Number(next + cur.num, cur.count + 1));
                }
            }
        }

        return isVisited;
    } // End of BFS()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        max = arr[N - 1];
        K = Integer.parseInt(br.readLine());
    } // End of input()
} // End of Main class