[SWEA] 8275. 햄스터 (백트래킹/Java)

[SWEA] 8275. 햄스터

 

📌 풀이 과정

1. 각 우리에 0부터 X마리까지 가능한 햄스터 수를 배치하기 위해 중복 순열을 생성한다.

2. (idx == N)이 되면 해당 순열이 경근이가 기록한 햄스터의 수에 모두 만족하는지 확인한다.

3. 조건을 모두 만족하면 현재 배치된 총 햄스터 수를 계산해, 기존 최대 햄스터 수를 갱신한다.

    조건을 하나라도 만족하지 못하는 경우 탐색을 종료하고, 다음 순열로 넘어간다.

 

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
	
	static int N, X, M;
	static int maxHamster;
	static int[] cage;
	static int[][] record;
	static int[] answer;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 햄스터 우리 
			X = Integer.parseInt(st.nextToken()); // 각 우리 최대 햄스터 마리수 
			M = Integer.parseInt(st.nextToken()); // 경근이의 기록 개수 
			cage = new int[N]; // 순열을 위한 배열 
			answer = new int[N]; // 최종 결과 저장 
			record = new int[M][3]; // 경근이 기록 저장
			maxHamster = Integer.MIN_VALUE;
			
			for(int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				record[i][0] = Integer.parseInt(st.nextToken()) - 1; // 시작 우리 
				record[i][1] = Integer.parseInt(st.nextToken()) - 1; // 끝 우리 
				record[i][2] = Integer.parseInt(st.nextToken()); // 햄스터 총 마리수 
			}
			
			perm(0);

			sb.append("#" + t + " ");
			if(maxHamster == Integer.MIN_VALUE) {
				sb.append(-1);
			}
			else {
				for(int i = 0; i < N; i++) {
					sb.append(answer[i] + " ");
				}
			}
			sb.append("\n");
		}

		System.out.print(sb.toString());
	}
	
	private static void perm(int idx) {
		if(idx == N) {
			for(int i = 0; i < M; i++) {
				int I = record[i][0]; // 시작 우리 
				int R = record[i][1]; // 끝 우리 
				int S = record[i][2]; // 햄스터 총 마리수 
				
				int sum = 0;
				for(int j = I; j <= R; j++) {
					sum += cage[j];
				}
				if(sum != S) return;
			}
			
			int total = 0;
			for(int i = 0; i < N; i++) {
				total += cage[i];
			}
			
			if(total > maxHamster) {
				maxHamster = total;
				answer = Arrays.copyOf(cage, N);
			}
			
			return;
		}
		
		for(int i = 0; i <= X; i++) {
			cage[idx] = i;
			perm(idx + 1);
		}
	}
}