정범의 프로그래밍 블로그 입니다.

4 분 소요

1. 문제 접근 방법 및 아이디어

이 문제는 모든 가능한 햄스터의 배치 중 조건을 만족하면서 합이 최대인 경우를 찾는 것이 핵심입니다.

  1. 배치 생성
    • 각 우리(1 ~ N)에 들어갈 수 있는 햄스터 수는 0마리부터 X까지 입니다.
  2. 모든 경우의 수 계산
    • 우리 개수(N)가 최대 6개, 햄스터 최대 수(X)가 10이므로, 한 우리당 11가지 경우가 가능합니다.
    • 전체 경우의 수는 11^6이므로, 완전 탐색이 가능합니다.
  3. 조건 검증
    • 기록된 M개의 조건(l번부터 r번 우리까지의 합이 s)을 모두 만족하는지 확인합니다.
  4. 최적화 갱신
    • 조건을 만족하는 배치 중 햄스터 총합이 최대인 것을 찾습니다.
    • 합이 같다면 사전순으로 앞선 것을 선택합니다.


2. 필요 개념 및 알고리즘

  1. 중복 순열
    • 각 우리에 0부터 X까지의 숫자를 중복해서 배치해야 하기 때문입니다.
    • N과 X의 범위가 최대 6개, 햄스터 최대 수 10이기 때문에 지수 시간 복잡도를 갖는 알고리즘을 사용해도 된다는 강력한 신호입니다.
  2. 조건 검증
    • M개의 제한 사항을 모두 통과해야 정답 후보가 됩니다.


3. 어려웠던 점

  1. 문제 의도 파악
    • 중복 순열 문제인지 파악하지 못했습니다.
  2. 배열 복사
    • result = numbers로 하면 주소값만 복사되어 값이 게속 변합니다.
    • 배열 복사 방법인 numbers.clone()을 생각하지 못했습니다.
  3. 배치 불가능 처리
    • 조건을 만족하는 경우가 단 하나도 없을 때 -1을 출력하는 예외 처리를 잊으면 안됩니다.


4. 코드 풀이

4.1 모든 경우의 수 계산

for (int i = 0; i <= X; i++) {
	numbers[level] = i;
	dfs(level + 1, cursum + i);
}
  • 각 우리(1 ~ N)에 들어갈 수 있는 햄스터 수는 0마리부터 X까지 입니다.
  • 우리 개수(N)가 최대 6개, 햄스터 최대 수(X)가 10이므로, 한 우리당 11가지 경우가 가능합니다.

4.2 조건 검증

// 모든 조건 체크하는 함수
static boolean ischeck() {

	// 모든 조건 탐색
	for (int[] it : list) {
		int l = it[0];
		int r = it[1];
		int s = it[2];

		// 햄스터의 총 수
		int sum = 0;

		// l번 우리에서 r번 우리까지의 햄스터의 수 계산
		for (int idx = l; idx <= r; idx++) {
			sum += numbers[idx];
		}

		// 기록에 일치하지 않으면 false 리턴
		if (sum != s)
			return false;
	}

	return true;
}
  • 기록된 M개의 조건(l번부터 r번 우리까지의 합이 s)을 모두 만족하는지 확인합니다.

4.3 최적화 갱신

if (level == N + 1) {
	if (ischeck()) {
	    // 햄스터 수가 가장 많은 것을 갱신한다.
	    if (cursum > maxcount) {
		    maxcount = cursum;
		    result = numbers.clone();
	    }   

	}
    return;
}
  • 조건을 만족하는 배치 중 햄스터 총합이 최대인 것을 찾습니다.
  • 합이 같다면 사전순으로 앞선 것을 선택합니다.
    • 0 ~ X 까지 오름차순으로 DFS를 돌리면 자연스럽게 가장 먼저 발견된 최대합 케이스가 사전순 최적해가 됩니다.

4.4 DFS 함수 코드

// 햄스터 배치 함수
static void dfs(int level, int cursum) {

	// 종료 조건
	if (level == N + 1) {
	    if (ischeck()) {
	        // 햄스터 수가 가장 많은 것을 갱신한다.
	        if (cursum > maxcount) {
		        maxcount = cursum;
		        result = numbers.clone();
	        }   

	    }
        return;
    }

	// 중복 순열
	for (int i = 0; i <= X; i++) {
		numbers[level] = i;
		dfs(level + 1, cursum + i);
	}
}
  • 이전 문제에서 풀었을 때는 cursum을 매개변수로 갖지 않고, 종료 조건에 도달하면 햄스터의 총합을 계산했습니다.
  • 매개변수를 사용하면 연산의 시간을 줄일 수 있습니다.

4.5 전체 코드

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

public class Solution_D4_8275_햄스터 {

	// 우리의 개수, 최대 햄스터의 수, 경근이의 기록의 수
	static int N, X, M;

	// l번 우리, r번 우리, 목표 햄스터 수
	static int l, r, s;

	static int[] numbers; // 우리 속 햄스터 수 모음
	static int maxcount; // 가장 많은 햄스터 수
	static int[] result; // 우리에 있는 햄스터 수
	static ArrayList<int[]> list; // 기록 리스트

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine().trim());

		// tc 수행
		for (int tc = 1; tc <= T; tc++) {

			// 우리의 개수, 최대 햄스터의 수, 경근이의 기록의 수 입력
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			X = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			// 초기화
			numbers = new int[N + 1];
			maxcount = Integer.MIN_VALUE;
			result = null;
			list = new ArrayList<int[]>();

			// l번 우리, r번 우리, 목표 햄스터 수
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				l = Integer.parseInt(st.nextToken());
				r = Integer.parseInt(st.nextToken());
				s = Integer.parseInt(st.nextToken());

				// list 추가
				list.add(new int[] { l, r, s });
			}

			// 처리
			dfs(1, 0);

			// 출력 내용 추가
			sb.append("#" + tc + " ");

			// 햄스터 배치가 불가능하면 -1을 추가
			// 햄스터 배치가 가능하면 1~N번 우리의 순서대로 우리에 있는 햄스터 수를 추가
			if (result == null) {
				sb.append("-1");
			} else {
				for (int i = 1; i <= N; i++) {
					sb.append(result[i] + " ");
				}
			}

			sb.append("\n");

		} // tc 종료

		// 출력
		System.out.println(sb);
	} // 메인 종료

	// 햄스터 배치 함수
	static void dfs(int level, int cursum) {

		// 종료 조건
		if (level == N + 1) {

			if (ischeck()) {

				// 햄스터 수가 가장 많은 것을 갱신한다.
				if (cursum > maxcount) {
					maxcount = cursum;
					result = numbers.clone();
				}

			}

			return;
		}

		// 중복 순열
		for (int i = 0; i <= X; i++) {
			numbers[level] = i;
			dfs(level + 1, cursum + i);
		}

	}

	// 모든 조건 체크하는 함수
	static boolean ischeck() {

		// 모든 조건 탐색
		for (int[] it : list) {
			int l = it[0];
			int r = it[1];
			int s = it[2];

			// 햄스터의 총 수
			int sum = 0;

			// l번 우리에서 r번 우리까지의 햄스터의 수 계산
			for (int idx = l; idx <= r; idx++) {
				sum += numbers[idx];
			}

			// 기록에 일치하지 않으면 false 리턴
			if (sum != s)
				return false;

		}

		return true;
	}

}

카테고리:

업데이트:

참고

현주가 좋아하는 제곱근 놀이

2 분 소요

1. 문제 접근 방법 및 아이디어 이 문제의 핵심은 숫자 N을 2로 만드는 가장 빠른 방법을 찾는 것입니다. 그리디 N이 완전제곱수라면 무조건 루트를 씌우는 것이 이득입니다. 숫자가 비약적으로 작아지기 때문입니다. 점프 ...

햄버거 다이어트

2 분 소요

1. 문제 접근 및 아이디어 이 문제는 주어진 재료들을 사용하거나, 사용하지 않거나를 결정하여 제한 칼로리 내에서 최대 점수를 뽑아내는 것이 핵심입니다. 입력 데이터 구조화 각 재료의 점수와 칼로리를 쌍으로 묶어 저장합니다. 선택의 기로 ...

수제 버거 장인

3 분 소요

1. 문제 접근 방법 및 순서 이 문제는 특정 재료들을 함게 넣을 수 없다는 제약 조건이 걸린 부분 집합 구하기 문제입니다. 제약 사항 정리 인접 행렬을 활용해서 어떤 재료 조합이 불가능한지 저장합니다. 재귀적 탐색 1...

위상 정렬 공부 (java)

2 분 소요

위상 정렬 알고리즘 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미합니다. 모든 원소를 방문하기 전에 큐가 비게 된다면 사...