[삼성 SW Expert Academy] 8275. 햄스터 [JAVA]

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

---

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

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

---

| 풀이

1. Step : 까다로운 조건을 보고, 완탐을 해야겠다고 느꼈다.
2. Step : 시간복잡도 체크 했다.
3.  

  4. 따라서, 0번 우리부터 쭉 들어가면서 중복순열 ? / DFS 방식
  5. 각 조건 체크하고
  6. 총 햄스터 수가 가장 큰 거 위주로 정렬하고 ( MAX )
  7. 가장 큰 햄스터의 수가 같을 경우, 오름차순 정렬 된 것을 답으로 한다.

---

| 어려웠던 점

   1. 코드 간단하게 하려고 했다가, 같은 메모리를 참조하게 해놨다는 걸 놓쳐서 50분 헤멨다.

  2. isFirst() // 사전순 체크 하는 함수에서, return true; ==> false 순으로 했는데 그렇게 하면 안된다.

   

  3. 아래처럼 해결했다.

---

| 코드

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

public class 햄스터_8725 {

	static int Tc, N, X, M, li, ri, si, max; 
	static int[] cage, ans;
	static ArrayList<Condition> condition;
	static boolean find; 
	private static class Condition{
		int from;
		int to;
		int number;
		
		public Condition(int from, int to, int number) {
			this.from = from;
			this.to = to;
			this.number = number;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
				
		st = new StringTokenizer(br.readLine(), " ");
		
		Tc = Integer.parseInt(st.nextToken());
		
		for( int tc =1 ; tc<=Tc; tc++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken()); // 총 우리의 수 
			X = Integer.parseInt(st.nextToken()); // 각 우리에 최대 X 마리 , 최소 0 마리
			M = Integer.parseInt(st.nextToken()); // 조건의 갯수
			
			cage = new int[N]; // cage : 각 우리에 들어있는 햄스터의 수
			ans = new int[N];
			condition = new ArrayList<>(); // 조건들 저장해놓은 곳
			max = Integer.MIN_VALUE; // 총 햄스터의 가장 큰 수 
			find = false;
			
			for( int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				li = Integer.parseInt(st.nextToken())-1; // li번 우리부터
				ri = Integer.parseInt(st.nextToken())-1; // ri번 우리까지
				si = Integer.parseInt(st.nextToken()); // 총 si 마리 <= 60 
				
				condition.add(new Condition(li, ri, si));
			}
			
			// step 1 : 0번 우리부터 0마리 씩 채우면서 총 X 마리까지 채우면서 DFS 
			solve(0,0);
			System.out.print("#"+tc+" ");
			if ( find ) {
				for( int i=0; i<N; i++) {
					System.out.print(ans[i] + " ");
				}
				System.out.println();
			}
			else {
				System.out.println("-1");
			}
		}
	}
	/*
	 * index : cage 번호
	 * Hnumber = hamseter 총 개수
	 */
	private static void solve(int index, int Hnumber) {
		
		// base condition // 다 채웠을 때
		if( index == N) {
			// 조건에 충족한다면?
			if( isOk() ) {
				// 총 햄스터의 개수 가장 큰 걸로
				if ( max < Hnumber ) {
					max = Hnumber;
					// 일단 정답 저장
					
					for( int i=0; i<N; i++) {
						ans[i] = cage[i];
					}
				} 
				// 햄스터의 개수 같고, 사전 순으로 앞에 오는게 있으면?
				else if ( max == Hnumber && isFirst()) {
					for( int i=0; i<N; i++) {
						ans[i] = cage[i];
					}
				}
				find= true;
			}
			// 그 중에서 햄스터의 개수 같으면, 사전순으로 정렬된것을 ans 배열에 저장하자.
			return;
		}
		
		// go 각 우리마다, 총 X마리까지
		for( int i=0; i<=X; i++) {
			cage[index] = i;
			solve(index+1, Hnumber+i);
		}
	}
	// 새로운 경우의 수가 사전 순으로 앞에 배열된 것이라면?
	private static boolean isFirst() {
		
		for( int i=0; i<N; i++) {
			if( cage[i] > ans[i]) {
				return false;
			}
		}
		
		return true;
	}
	
	// 조건에 충족하는지 검사하기
	private static boolean isOk() {
		
		for( int i=0; i<condition.size(); i++) {
			int from = condition.get(i).from; // from 우리부터
			int to = condition.get(i).to; // to 우리까지
			int Total = condition.get(i).number; // Total 개수의 햄스터 개수 이어야해
			int count =0;
			for( int start = from; start<=to; start++) {
				count += cage[start];
			}
			if( count != Total ) {
				return false;
			}
		}
		
		return true;
	}
}

---

| 보완할 점

 - 메모리 참조 꼼꼼히,

 - 조건 체크할 때 false -> true // true -> false 순서도 큰 영향 미친다.

---