백준 16938번: 캠프 준비

문제

https://www.acmicpc.net/problem/16938

16938번: 캠프 준비

---

풀이

이 문제에서의 알고리즘 캠프를 여는 기준은 다음과 같습니다.

1. 문제는 2문제 이상이어야 한다.
2. 난이도의 합은 L 이상, R 이하여야 한다.
3. 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이는 X 이상이어야 한다.

캠프에 사용할 문제를 고르는 경우의 수를 구해야 하는 문제이며 dfs를 이용하여 해결하였습니다.

---

코드

C언어

모든 입력을 받은 후에 qsort 함수를 이용하여 각 문제의 난이도가 담긴 정수 배열 arr를 정렬한 후에 dfs 함수를 실행합니다. 이때 함수의 매개변수는 처음부터 탐색하기 위해 idx와 dpth는 0으로, 최댓값과 최솟값을 비교하기 위해 min과 max는 각각 INT_MAX, 0으로, 선택된 문제들의 난이도의 합을 구하기 위해 sum은 0으로 설정합니다.

dfs 함수에서 i를 포함한 for문을 이용하여 함수의 매개변수인 idx부터 탐색을 시작합니다. 이때 tmp_min과 tmp_max에 각각 최솟값과 최댓값을 저장한 뒤에 dfs를 재귀적으로 실행할 때 매개변수로 사용합니다. 또한 중복된 문제를 선택하지 않게 하기 위해 idx + 1을, 문제를 선택했다는 의미로 dpth + 1을, sum에 선택된 문제의 난이도를 더한 값을 매개변수로 사용합니다.

dpth가 2보다 크거나 같으면 2문제 이상 선택했다는 뜻으로 1번 규칙을 만족하기 때문에 2번과 3번 규칙을 만족한다면 cnt에 1을 더하게 됩니다.

위의 과정이 끝나면 main 함수에서 cnt의 값을 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define math_max(a, b) a > b ? a : b
#define math_min(a, b) a < b ? a : b
int n, l, r, x, cnt = 0, *arr;
int compare(const void* a, const void* b) {
	int o1 = *(int*)a;
	int o2 = *(int*)b;
	if (o1 > o2) return 1;
	else if (o1 < o2) return -1;
	else return 0;
}
void dfs(int idx, int dpth, int min, int max, int sum) {
	if (dpth >= 2) {
		if (l <= sum && sum <= r && max - min >= x) {
			cnt++;
		}
	}
	for (int i = idx; i < n; i++) {
		int tmp_min = math_min(min, arr[i]), tmp_max = math_max(max, arr[i]);
		dfs(i + 1, dpth + 1, tmp_min, tmp_max, sum + arr[i]);
	}
}
main() {
	scanf("%d %d %d %d", &n, &l, &r, &x);
	arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	qsort(arr, n, sizeof(int), compare);
	dfs(0, 0, INT_MAX, 0, 0);
	printf("%d", cnt);
}

자바

위의 C언어를 이용한 풀이와 동일한 방법으로 arr를 정렬할 때 java.util.Arrays 클래스의 sort 메서드를 사용했습니다.

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

public class Main {

    static int n, l, r, x, cnt = 0;
    static int[] arr;

    public static void dfs(int idx, int dpth, int min, int max, int sum) {
        if (dpth >= 2) {
            if (l <= sum && sum <= r && max - min >= x) {
                cnt++;
            }
        }
        for (int i = idx; i < n; i++) {
            dfs(i + 1, dpth + 1, Math.min(min, arr[i]), Math.max(max, arr[i]), sum + arr[i]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        dfs(0, 0, Integer.MAX_VALUE, 0, 0);
        System.out.println(cnt);
    }
}

 

---

결론

C언어를 이용하여 이 문제를 해결할 때 #define을 이용하여 최댓값과 최솟값을 구하기 위한 매크로 함수를 만들었습니다. 하지만 어떤 이유에서인지 tmp_max와 tmp_min을 따로 선언하지 않고 dfs(i + 1, dpth + 1, math_min(min, arr[i]), math_max(max, arr[i]), sum + arr[i])와 같이 코드를 작성했을 때 시간이 너무 오래 걸리는 문제가 발생했습니다.

이후에 왜 이런 현상이 발생하는지에 대해 알게 된다면 따로 글을 써보도록 하겠습니다.