햄스터

문제

SW Expert Academy

문제 설명

정우는 햄스터를 많이 기르고 있는데, 햄스터들에게 별 관심을 가지고 있지는 않다. 정우는 햄스터 우리를 N개 가지고 있으며, 각 우리에 1번에서 N번까지의 번호를 붙여 일렬로 놔두고 있다. 정우는 햄스터들에게 별 관심이 없지만, 각 우리에 0마리 이상 X마리 이하의 햄스터가 있다는 것은 알고 있다. 어느 날 경근이가 정우 집에 놀러 왔다. 경근이는 바쁜 정우와 노는 대신 햄스터의 수를 세면서 놀았다. 경근이는 M개의 기록을 남겼는데, 각 기록은 “l번 우리에서 r번 우리까지의 햄스터 수를 세었더니 s마리였다.” 하는 내용들이다. 경근이가 남긴 기록을 모두 만족하는 햄스터 수 배치를 구하는 프로그램을 작성하라.

제한 사항

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 N, X, M(1 ≤ N ≤ 6, 1 ≤ X, M ≤ 10)이 공백 하나로 구분되어 주어진다.

다음 M개의 줄의 i번째 줄에는 세 정수 li, ri, si(1 ≤ li ≤ ri ≤ N, 0 ≤ si≤ 60)가 공백 하나로 구분되어 주어진다.

이는 li번 우리에서 ri번 우리까지의 햄스터 수를 세었더니 si마리였다는 것을 나타낸다.

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 각 테스트 케이스마다 모든 기록을 만족하는 햄스터 수 배치가 있다면, 1번 우리부터 N번 우리의 순서대로 우리에 있는 햄스터 수를 공백 하나로 구분하여 출력한다. 만약 가능한 방법이 여러 가지일 경우, 햄스터 수가 가장 많은 것을 출력한다. 그래도 가능한 방법이 여러 가지일 경우, 사전순으로 가장 앞선 것을 출력한다. 예를 들어, 9 10 10 가 10 9 10 보다 더 앞선 순서이다. 만약 모든 기록을 만족하는 햄스터 배치가 없다면, -1을 출력하도록 한다.

입출력 예

입력	출력
3
3 5 1
1 2 5
3 5 2
1 2 6
2 3 7	#1 0 5 5
4 5 2	#2 4 2 5
1 3 15	#3 -1
3 4 4

아이디어

제출 코드

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

/*
 @author ranuinclulus
 @since 2024.08.13
 @link
 @timecomplex
 @performance 30748 304
 @category #dfs
 @note
 */
public class four8275 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int n;
    static int x;
    static int m;
    static int[][] records;
    static int[] houses;
    static List<int[]> list;

    public void solution() throws IOException {
        int testNum = Integer.parseInt(br.readLine());
        for (int test = 1; test <= testNum ; test++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            records = new int[m][3];
            houses = new int[n + 1];
            list = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 3; j++) {
                    // records[i][0] 에서 records[i][1]까지 records[i][2]마리 
                    records[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append('#').append(test).append(' ');
            dfs(0, 0);
            if (!list.isEmpty()) {
                Collections.sort(list, new Comparator<int[]>() {

                    @Override
                    public int compare(int[] o1, int[] o2) {
                        return -Integer.compare(o1[n], o2[n]);
                    }
                });
                for (int i = 0; i < n; i++) {
                    sb.append(list.get(0)[i]).append(' ');
                }
            } else {
                sb.append(-1);
            }
            sb.append('\n');
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private void dfs(int depth, int totalSum) {
        
        for(int[] record : records) {
            int sum = 0;
            if (depth < record[1]) continue;
            for (int i = record[0] - 1; i <= record[1] - 1; i++) {
                sum += houses[i];
            }
            if (sum != record[2]) {
                return;
            }
        }

        if (depth == n) {
            houses[n] = totalSum;
            list.add(houses.clone());
            return;
        }

        for (int i = 0; i <= x ; i++) {
            houses[depth] = i;
            dfs(depth + 1, totalSum + i);
            houses[depth] = 0;
        }
        
    }

    public static void main(String[] args) throws IOException {
        new four8275().solution();
    }
}