문제

지문

정우는 햄스터를 많이 기르고 있는데, 햄스터들에게 별 관심을 가지고 있지는 않다.
정우는 햄스터 우리를 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을 출력하도록 한다.

입출력 예시

입력

2 -> TC 개수
3 5 1 -> N X M
1 2 5 -> l r s
//첫번째 TC 끝
3 5 2
1 2 6
2 3 7
//두번째 TC 끝
4 5 2
1 3 15
3 4 4
//세번째 TC
.

출력

#1 0 5 5
#2 4 2 5
#3 -1

문제 정리

목표

조건을 만족하는 크기n의 배열을 구하라

조건

1. 조건(기록지)에 부합하는 조합 중 전체 값이 가장 많은 것 출력
2. 사전순으로 가장 앞선 것 출력
3. 모든 기록 만족하는 조합 없으면 -1 출력

아이디어

변수 설정

[입력 변수]
int T //test case 개수
int N //햄스터 우리 개수
int X //각 우리에 있을 수 있는 최대 햄스터 수
int M //우리 및 햄스터 정보 기록 수
////////우리 및 햄스터 정보 기록
//l번 우리에서 r번 우리까지의 햄스터 s마리
int l //기록 시작점 우리 번호
int r //기록 끝점 우리 번호
int s //l번 우리부터 r번까지의 햄스터 수
.
[추가 변수]
int[][] cntDocu //기록한 결과 담을 배열
//[][0]:카운트 시작 인덱스 | [][1] : 카운트 끝 인덱스 | [][2] : 총 햄스터 수
int maxHamster //조합에 대해 가장 많은 햄스터 수
int[] hamsterTemp //햄스터 배치 임시 저장
.
[출력 변수]
StringBuilder ans //출력할 답안. 조건 부합 답 없다면 -1

고려 사항

• 조건에 부합하는 배치가 있을 때 출력값 조건
  • 1.햄스터 수가 가장 많은 것 출력
  • 2.햄스터 수가 많다면 사전순으로 가장 앞선 것
    => 위 고려 순서를 지켜야 함
• 조건 만족하는 배치가 없는 경우 -> 출력값 : -1
  • 각 기록지를 모두 만족하는 경우 없을 때
    • ex) 아래 케이스의 경우
      1번 기록지 - 1 3 15 => 1번 우리부터 3번까지 15마리 -> 각 우리에 5마리씩
      2번 기록지 -> 3 4 4 => 3번 우리부터 4번까지 4마리 -> 위 조건 하에서 이미
      (3번 우리에 있는 햄스터 수) >4
      => 조건을 모두 만족할 수 없음 = -1 출력

4 5 2
1 3 15
3 4 4 

필요 로직

• 계산 최대 크기는 11^6 = (우리 당 햄스터 수 X(0<=X<=10))^(우리 개수 N(<=6))
  => DFS로 풀어도 되겠다!
• 각 조합에 대해 조건을 만족하는지 여부를 따지면 되겠다!
  • 종료조건 부분에 조건(기록지) 부합 여부 탐색 로직
• 조건에 부합한다면, 즉, 정답 후보라면
  • 1.햄스터 수 카운트하여 현재 최댓값과 비교
    • 1-1. 이 때, 햄스터 우리 수는 1부터 시작이므로 인덱스에 주의
  • 2. 현재 최댓값보다 많다면 정답 업데이트
    • 2-1. 이 때, 햄스터 수가 같더라도, 항상 사전순으로 조합이 만들어지기 때문에 사전순으로 출력하여야 한다는 조건은 생각하지 않아도 됨

코드

전체 코드

package day0311;

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

public class D4_8275_2 {
	static int n; // 우리 수
	static int x; // 각 우리에 있을 수 있는 최대 햄스터 수
	static int m; // 기록 수

	// 기록 관련 변수
	static int l; // 카운트 시작 우리 번호
	static int r; // 카운트 끝 우리 번호
	static int s; // 카운트한 햄스터 수
	static int[][] cntDocu; // 기록한 결과

	static int maxHamster; // 가장 많은 햄스터 수
	static int[] hamsterTemp; // 케이스별 임시 저장 배열
	static StringBuilder ans; // 출력할 답안

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


		int t = Integer.parseInt(br.readLine().trim());
		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());

			hamsterTemp = new int[n];
			cntDocu = new int[m][3]; // 카운트 시작 인덱스, 카운트 끝 인덱스, 총 햄스터 수
			maxHamster = Integer.MIN_VALUE;

			ans = new StringBuilder();

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				cntDocu[i][0] = Integer.parseInt(st.nextToken());
				cntDocu[i][1] = Integer.parseInt(st.nextToken());
				cntDocu[i][2] = Integer.parseInt(st.nextToken());
			}

			// 입력 끝
			hamsterCase(0);

			if (ans.length() == 0) {
				ans.append("-1");
			}

			System.out.println("#" + tc + " " + ans);

		} // tc 끝

	}// main 끝

	static void hamsterCase(int N) {

		// 종료조건
		if (N == n) {
			hamsterCal(N);
			return;
		}

		// 재귀조건
		for (int i = 0; i <= x; i++) {
			hamsterTemp[N] = i;
			hamsterCase(N + 1);
		}

	}

	static void hamsterCal(int a) {
		// 조건 탐색
		int nowHamster = 0; // 현재 조합의 햄스터 수
		for (int i = 0; i < n; i++) {
			nowHamster += hamsterTemp[i];
		}

		if (nowHamster > maxHamster) { // 기록 조건 검색
			boolean flag = false;

			for (int i = 0; i < m; i++) {
				int tempL = cntDocu[i][0];
				int tempR = cntDocu[i][1];
				int tempS = cntDocu[i][2];

				int tempCnt = 0;

				for (int j = tempL - 1; j <= tempR - 1; j++) {
					tempCnt += hamsterTemp[j];
				}
				if (tempCnt == tempS) {
					flag = true;
				} else {
					flag = false;
					break;
				}

			}
			if (flag) {
				maxHamster = nowHamster;
				ans.delete(0, ans.length());
				for (int i = 0; i < n; i++) {
					ans.append(hamsterTemp[i] + " ");
				}
			}

		}
		return;
	}

}

상세 코드

기록 저장

cntDocu = new int[m][3]; // 카운트 시작 인덱스, 카운트 끝 인덱스, 총 햄스터 수
for (int i = 0; i < m; i++) {
	st = new StringTokenizer(br.readLine());
	cntDocu[i][0] = Integer.parseInt(st.nextToken());
	cntDocu[i][1] = Integer.parseInt(st.nextToken());
	cntDocu[i][2] = Integer.parseInt(st.nextToken());
}

.

햄스터 배치 조합 만드는 재귀

static void hamsterCase(int N) {

	// 종료조건
	if (N == n) {
		hamsterCal(N);
		return;
	}

	// 재귀조건
	for (int i = 0; i <= x; i++) {
		hamsterTemp[N] = i;
		hamsterCase(N + 1);
	}

}

조건 부합 여부 탐색

static void hamsterCal(int a) {
	// 조건 탐색
	int nowHamster = 0; // 현재 조합의 햄스터 수
	for (int i = 0; i < n; i++) {
		nowHamster += hamsterTemp[i];
	}

	if (nowHamster > maxHamster) { // 기록 조건 검색
		boolean flag = false;

		for (int i = 0; i < m; i++) {
			int tempL = cntDocu[i][0];
			int tempR = cntDocu[i][1];
			int tempS = cntDocu[i][2];
			int tempCnt = 0;

			for (int j = tempL - 1; j <= tempR - 1; j++) {
				tempCnt += hamsterTemp[j];
			}
			if (tempCnt == tempS) {
				flag = true;
			} else {
				flag = false;
				break;
			}

		}
		if (flag) {
			maxHamster = nowHamster;
			ans.delete(0, ans.length());
			for (int i = 0; i < n; i++) {
				ans.append(hamsterTemp[i] + " ");
			}
		}

	}
	return;
}

다른 방법

가지치기

• 현재 값을 채운 인덱스가 어떤 기록의 마지막값이라면,
  • 해당 기록 조건을 탐색하고 비교하여 가지치기한다.

햄스터 수 최댓값인 조합부터 탐색

• 해당 문제는 조건(기록)을 만족하는 최댓값 조합 을 출력해야 함.
  => 만들 수 있는 내부 합이 최댓값인 조합부터 탐색했다면 더 효율적일 것.

DP

• 해당 조합에 대해 현재 인덱스까지의 누적값을 저장
  • 현재 인덱스가 어떤 기록의 마지막 인덱스라면 값 비교

가지치기 위치 바꾼 코드

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

public class D4_8275{
	static int n; // 우리 수
	static int x; // 각 우리에 있을 수 있는 최대 햄스터 수
	static int m; // 기록 수

	// 기록 관련 변수
	static int l; // 카운트 시작 우리 번호
	static int r; // 카운트 끝 우리 번호
	static int s; // 카운트한 햄스터 수
	static int[][] cntDocu; // 기록한 결과

	static int maxHamster; // 가장 많은 햄스터 수
	static int[] hamsterTemp; // 케이스별 임시 저장 배열
	static StringBuilder ans; // 출력할 답안

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


		int t = Integer.parseInt(br.readLine().trim());
		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());

			hamsterTemp = new int[n];
			cntDocu = new int[m][3]; // 카운트 시작 인덱스, 카운트 끝 인덱스, 총 햄스터 수
			maxHamster = Integer.MIN_VALUE;

			ans = new StringBuilder();

			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				cntDocu[i][0] = Integer.parseInt(st.nextToken());
				cntDocu[i][1] = Integer.parseInt(st.nextToken());
				cntDocu[i][2] = Integer.parseInt(st.nextToken());
			}

			// 입력 끝
			hamsterCase(0);

			if (ans.length() == 0) {
				ans.append("-1");
			}

			System.out.println("#" + tc + " " + ans);

		} // tc 끝

	}// main 끝

	static void hamsterCase(int N) {

		//가지치기
		for(int i = 0;i<m;i++){
			int tempL = cntDocu[i][0];
			int tempR = cntDocu[i][1];
			int tempS = cntDocu[i][2];

			//현재 기록의 범위가 이미 다 채워졌다면
			if(N>=tempR){
				int tempCnt = 0;
				for (int j = tempL - 1; j <= tempR - 1; j++) {
					tempCnt += hamsterTemp[j];
				}
				if(tempCnt!=tempS) return;
			}
		}

		// 종료조건
		if (N == n) {
			hamsterCal();
			return;
		}

		// 재귀조건
		for (int i = 0; i <= x; i++) {
			hamsterTemp[N] = i;
			hamsterCase(N + 1);
		}

	}

	static void hamsterCal() {

		// 조건 탐색
		int nowHamster = 0; // 현재 조합의 햄스터 수
		for (int i = 0; i < n; i++) {
			nowHamster += hamsterTemp[i];
		}

		if (nowHamster > maxHamster) { // 기록 조건 검색

			maxHamster = nowHamster;
			ans.delete(0, ans.length());
			for (int i = 0; i < n; i++) {
				ans.append(hamsterTemp[i] + " ");
			}


		}
		return;
	}

}

성능 비교

• BufferedReader + 가지치기
  

• BufferedReader + DFS
  

• Scanner + DFS
  

정리

• 하나의 문제를 정말 다양한 방법으로 풀 수 있다
• 필요 변수가 많아질 때 신경쓸 것이 매우 많아진다
  • 변수명, 인덱스 등등....
• 지문이 길다면 필요한 내용을 컴팩트하게 정리하는 것이 필요
• 가지치기의 영향이 정말 크다!
  • 같은 코드 구성이더라도 흐름에 따라 성능에 영향을 많이 준다
  • 로직을 깔끔하게 하기 위해 많은 문제를 풀어보는 것이 중요할 것