[SWEA/JAVA] 8275 - 햄스터

문제 정보

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWxQ310aOlQDFAWL

 

문제

 

문제 해결 과정

완전 탐색 풀이

1) 각 우리별 햄스터 숫자 순열 생성

각 우리별로 최소 0마리 최대 x마리의 햄스터를 배치할 수 있고, 이러한 우리가 n개가 있다고 하였다. 각 우리별로 햄스터 숫자를 배치하는 순열을 만들어 보면 경우의 수는 다음과 같다.

1번 우리(0~x마리 → x개) * 2번 우리(0~x마리 → x개) * ... * n번 우리(0~x마리 → x개) = x^n가지

 

x는 최대 10이고 n은 최대 6이라고 하였으므로, 우리별로 햄스터 숫자를 배치하는 순열의 경우의 수는 10^6이 된다. (정확히는 0~x마리는 x+1개이므로  11^6일 것이다.)

 

2) 생성된 순열에 대해, 기록이 맞는지 확인

만든 순열에 대해 m번의 기록을 보며, [l, r]번 우리의 햄스터 수의 합이 s마리인지 확인하는 작업을 진행한다고 생각하자. m은 최대 10이고, 구간 [l, r]의 최대 크기는 우리의 크기인 n과 같다. 따라서, 시간복잡도는 10^6 * m * n = 10^6 * 10 * 6 = 6 * 10^7이되므로, 시간복잡도 내에 풀 수 있다.

 

코드

class Main {
	static int n; // 우리의 개수
	static int max; // 각 우리의 최대 햄스터 수
	static int m; // 기록의 수
	static int[] arr; // 임시 각 우리별 햄스터의 개수
	static int[][] record; // 기록들(시작, 끝, 햄스터 수 합)
	static int maxSum; // 햄스터 합의 최대
	static int[] result; // 정답 각 우리별 햄스터의 개수
	
	static void perm(int idx) { // 현재 idx 우리까지 햄스터 수 결정됨
		if(idx >= n) {	
			for(int i=0; i<m; i++) {
				int l = record[i][0];
				int m = record[i][1];
				int s = record[i][2];
				
				int sum = 0; // 햄스터 수의 합
				for(int j=l; j<=m; j++) {
					sum+= arr[j];
				}
				
				if(sum != s) return;
			}
			
			int total = 0;
			for(int i=0; i<n; i++) {
				total += arr[i];
			}
			
			if(total > maxSum) {
				maxSum = total;
				result = Arrays.copyOf(arr, n);
			}
			
			return;
		}
		
		for(int i=0; i<=max; i++) {
			arr[idx] = i;
			perm(idx+1);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
	   
		int tc = Integer.parseInt(br.readLine()); // 테스트 케이스 수
		for(int t=1; t<=tc; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken()); // 우리의 개수
			max = Integer.parseInt(st.nextToken()); // 각 우리의 최대 햄스터 수
			m = Integer.parseInt(st.nextToken()); // 기록의 수
			maxSum = -1;
		   
			arr = new int[n]; // 각 우리별 햄스터의 개수 (임시)
			result = new int[n]; // 각 우리별 햄스터의 개수 (최종)
			record = new int[m][3]; // 기록들(시작, 끝, 햄스터 수 합)
			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()); // 햄스터 개수 합
			}
		   
			sb.append("#" + t + " ");
			
			perm(0);

			if(maxSum >= 0) {
				for(int i=0; i<n; i++) {
					sb.append(result[i] + " ");
				}									
			} else {
				sb.append(-1);					
			}
			
			sb.append("\n");
		}
	   
		System.out.println(sb);
	}
}