백준 24884번 : 장작넣기 [자바]

 

🧫 문제 분석

 

✔️ 출처

장작넣기 골드 5

 

📖 문제

 

 

완전탐색 문제

 

문제를 이해하는데 조금 어려웠다.

처음 위치한 SKH의 위치에 대해서는 장작을 넣지 않는다.

그 다음 부터 넣는다.

 

화력감소때 넣은 장작의 위치는 감소시키지 않는 형태로 진행한다.

 

장작은 

왼쪽, 현재, 오른쪽으로 3가지를 탐색한다.

 

시간복잡도가 약 O(3^T * N)  정도 나오는 것 같다.

 

 

---

🔅 문제 풀이

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

public class Main {

    // 24884번 장작 넣기
    // T시간동안  최소 K개 유지

    static class Node {
        int SKH;
        int[] arr;
        int time;

        public Node(int firewoodNum, int[] arr, int time) {
            this.SKH = firewoodNum;
            this.arr = arr;
            this.time = time;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken()); // 모닥불 개수 <= 6
        int W = Integer.parseInt(st.nextToken()) + 1; // SKH 시작 모닥불 번호 1 ~ N
        int T = Integer.parseInt(st.nextToken()); // 모닥불 놀이 시간 <= 11
        int K = Integer.parseInt(st.nextToken()); // 최소 모닥불 개수   <= 6


        int[] arr = new int[N + 2];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(W, arr.clone(), 0));

        int answer = 0;

        while (!q.isEmpty()) {
            Node fire = q.poll();

            fire.time++;

            // 화력 감소
            int[] old = fire.arr.clone(); // 반드시 복사해서 사용
            int[] next = new int[old.length];
            for (int i = 1; i <= N; i++) {
                // 화력 감소 -> 장작넣기 때문에 처음에는 장작 넣기 X
                if (fire.time > 1 && fire.SKH == i) {
                    next[i] = old[i];
                } else {
                    // 양 옆의 모닥불이 켜져있는지에 따른 화력 감소
                    int cnt = (old[i-1] > 0 ? 1 : 0) + (old[i+1] > 0 ? 1 : 0);
                    next[i] = old[i] - (3 - cnt);
                }
            }


            // T시각에는 이동하지 않고 장작도 안넣음, 화력감소는 됨
            if (fire.time == T) {
                long cnt = Arrays.stream(next).filter(x -> x > 0).count();
                // K개 이상이면 경우의 수 1 개 추가
                if (cnt >= K) answer++;
                continue;
            }

            // 장작 넣을 위치 탐색
            for (int i = fire.SKH - 1; i <= fire.SKH + 1; i++) {
                if (i < 1 || i > N ) continue;

                q.offer(new Node(i, next, fire.time));
            }
        }

        System.out.println(answer);
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  복사해서 사용안하고 바로 화력감소해서 갱신된 값을 참조해서 다음 모닥불이 잘못된 계산을 하게 했다..
2.  다른 요소를 참조하거나 영향을 끼칠때는 원본을 복사해서 사용하자...