[Java] 백준 24884번 장작 넣기

브루트포스 문제입니다.

규칙에 맞게 장작을 넣어서 K개의 모닥불을 유지 시킬 수 있는 경우의 수를 구해야합니다.

현재 위치에서 [-1, 0, 1] 위치의 장작을 넣을 수 있습니다.
장작을 넣을 경우 해당 위치 1시간 동안 불이 줄어들지 않습니다.

화력 감소는 아래와 같습니다.
인접한 2곳에 불이 켜져있으면 -1
인접한 1곳에 불이 켜져있으면 -2
인접한 곳에 불이 없으면 -3

순서는 화력감소가 된 후에 장작 넣기가 진행됩니다.
=> 첫번째 시간에는 아직 장작을 넣은 것이 없기 때문에 모든곳에서 화력감소가 일어납니다.

진행 순서
1-1 현재 T시간 인 경우 경우의 수 +1, 4번으로
1-2 현재 T시간이 아닌 경우 2번으로 
2. 화력감소
3. 꺼진 개수 세기
4. [-1, 0, 1]에 장작넣기 -> 1번으로 이동

사용한 반례

4 2 3 3
8 0 6 100

ans = 0

 

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

public class Main {
  static int n;
  static int w;
  static int t;
  static int k;
  static int result;

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

    n = Integer.parseInt(st.nextToken());
    w = Integer.parseInt(st.nextToken());
    t = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());
    result = 0;
    int[] fire = new int[n];

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; ++i) {
      fire[i] = Integer.parseInt(st.nextToken());
    }

    dfs(w, 1, -1, fire);

    bw.write(result + "\n");
    bw.close();
  }

  public static void dfs(int loc, int time, int filter, int[] fire) {
    int cnt = 0;
    int[] move = { -1, 0, 1 };
    int[] temp = new int[n];

    cnt = fireCalc(filter, fire);

    if (cnt > n - k) {
      return;
    }

    if (time == t) {
      ++result;
      return;
    }

    for (int i = 0; i < 3; ++i) {
      copyArr(fire, temp);
      int nextLoc = loc + move[i];

      if (nextLoc < 0 || nextLoc >= n) {
        continue;
      }

      dfs(nextLoc, time + 1, nextLoc, temp);
    }
  }

  public static int fireCalc(int filter, int[] fire) {
    int prev = 0;
    int cnt = 0;
    boolean chk;
    for (int i = 0; i < n; ++i) {
      chk = false;

      if (filter == i) {
        if (fire[i] > 0) {
          prev = 1;
        } else {
          ++cnt;
          prev = 0;
        }
        continue;
      }

      if (fire[i] > 0) {
        chk = true;
      }

      fire[i] = prev == 0 ? fire[i] - 2 : fire[i] - 1;
      prev = chk ? 1 : 0;

      if (i + 1 < n) {
        fire[i] = fire[i + 1] == 0 ? fire[i] - 1 : fire[i];
      } else if (i + 1 == n) {
        fire[i] = fire[i] - 1;
      }

      if (fire[i] <= 0) {
        fire[i] = 0;
        ++cnt;
      }
    }

    return cnt;
  }

  public static void copyArr(int[] fire, int[] temp) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        temp[i] = fire[i];
      }
    }
  }
}