[c 알고리즘] DFS 실습 - 정올 (2167번) 책 꺼내기 part1

[정올 2167번 문제]

 

이번 문제는 DFS기법 중 조합 문제에 해당 된다. 입력 받은 n개의 숫자를 조합하여 합을 구해 책장의 높이를 초과하는 정도가 최소가 되는 것을 찾는 문제이다. 

 

DFS문제는 아래와 같은 순서로 생각해보는 것을 권장한다. 

1. 문제를 파악하여 Graph그리기
2. Graph의 각 노드마다 stack에 data가 어떻게 쌓이는지 확인하기
3. 입력 받은 값들의 관계가 어떻게 되는지 파악하기.

위와 같은 순서를 추천하는 가장 큰 이유는 DFS를 재귀함수로 구현하기 때문이다. data가 stack에 어떻게 저장 되는지 눈으로 보지 않으면 정말 파악하기 어렵다. 

반응형

 

[Graph 예시]

 

위 그래프를 보면, A[0]을 선택했을 때 A[1]을 선택하거나 A[2]를 선택하는 경우가 있다. 그 후 A[1]을 선택했을 때는 이미 앞에서 (A[1], A[2])를 조합하였기 때문에 A[1]은 선택하지 않고, A[2]만 선택하였다. 즉 선택한 위치에서 그 뒤에 값만 본다는 것을 의미한다. 

 

이제 위 내용을 책 꺼내기 문제에 적용시켜 어떻게 코드를 구성해야할지 확인해보자.

 

입력 예시를 보면 총 6개의 정수를 입력 받았다. 그리고 책장의 높이는 40이다.

 

6, 18, 11, 13, 19, 11 

 

우리가 알고 싶은 건 저 6개의 정수를 조합하여 40을 초과하는 정도가 최소가 되는 값을 구하고 싶다. 

 

6을 먼저 선택 했으면 그다음은 18선택, 11선택... 을 도식화 해보면 다음과 같다.

 

6 + 18 + 11 + 13 ... > 40 이렇게 되는 정수의 조합을 찾고 싶은 것이다.

 

즉 6개의 정수 중 x개를 뽑아, 그 합이 40보다 큰지 확인하는 것이다. 

 

그럼 어떻게 코드를 구현해야하는지 같이 확인해보자.

 

#include <stdio.h>
#define MAXN (20)
#define INF (1<<30)
int N, B;
int A[MAXN + 10];
int min_sum = INF; //최소 값을 찾기 위해 정수범위의 제일 큰 값으로 세팅


void InputData(void) {
	scanf("%d %d", &N, &B);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
}

int DFS(int n, int sum)
{
	if (sum >= B)
	{
		if (min_sum > sum)
		{
			
			min_sum = sum; // min_sum이 제일 작다고 가정했는데 
						   // 그것보다 작은게 나타나면 그게 제익 작은 값이니까
						   // min_sum을 업데이트해줌.
			
			return; 
		}
	}

	if (n >= N) return; // n이 범위를 초과했으니 리턴

	for (int i = n; i < N; i++)
	{
		DFS(i + 1, sum + A[i]); // 다음 번째만 보면서 간다.
	}
}

int main(void) {
	int T, ans = -1;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		InputData();//입력받는 부분
		min_sum = INF;// 테스트 케이스 마다 min_sum 초기화 필요
		DFS(0, 0);
		ans = min_sum - B;

		printf("%d\n", ans);
	}
	return 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1428&sca=99&page=12

JUNGOL