[BOJ] 백준 2309 일곱 난쟁이

출처: https://www.acmicpc.net/problem/2309  

Approach

완전탐색 유형 문제이다.

완전탐색 기법이란?

- 9명의 난쟁이 중에서 7명 선택해서 그 숫자의 합 = 100 이면 된다.

- 출력 시, 오름차순으로 해야 하기에 선택 전/후로 오름차순 정렬시켜준다.

 

▶ 순열과 조합  

순열과 조합 (백준 N과 M 시리즈)

▶ 중복 없는 Input Data에 중복없이 선택

[BOJ] 백준 15655 N과 M(6)

 

제출 코드 (조합 Ver.)

#include <stdio.h>

const int N = 9;
const int PICK = 7;
const int TOTAL = 100;
int ans[N], arr[N], trr[N], sum;
bool flag, visited[N];

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

void mergeSort(int start, int end) {
    // 0. base condition
    if (start >= end) return;
    // 1. divide
    int mid = (start + end) / 2;
    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j])
            trr[k++] = arr[i++];
        else
            trr[k++] = arr[j++];
    }
    while (i <= mid) trr[k++] = arr[i++];
    while (j <= end) trr[k++] = arr[j++];
    // 4. copy
    for (i = start; i <= end; ++i) {
        arr[i] = trr[i];
    }
}

void DFS(int idx, int depth) {
    if (flag)
    {
        return;
    }

    if (depth == PICK)
    {
        sum = 0;
        for (int i = 0; i < PICK; ++i)
        {
            sum += ans[i];
        }

        if (sum == TOTAL)
        {
            flag = true;
            for (int i = 0; i < PICK; ++i)
            {
                printf("%d\n", ans[i]);
            }
        }
        return;
    }

    for (int i = idx; i < N; ++i)
    {
        if (visited[i]) continue;
        
        visited[i] = true;
        ans[depth] = arr[i];

        DFS(i, depth + 1);

        visited[i] = false;
        ans[depth] = 0;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();
    mergeSort(0, N - 1);
    DFS(0, 0);
}

 

제출 코드 (C++)

또 다른 방법으로는 9명 중에서 두명을 제외하는 것을 생각해볼 수 있다.

9C7 = 9C2 = 36 이다.

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9;
const int TOTAL = 100;

int arr[N], sum;

void output(int tg1, int tg2)
{
    for (int i = 0; i < N; ++i)
    {
        if (tg1 == i || tg2 == i)
            continue;


        printf("%d\n", arr[i]);
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &arr[i]);
        sum += arr[i]; // 9명의 키
    }
    
    // 오름차순 정렬
    sort(arr, arr + N);

    for (int tg1 = 0; tg1 < N; ++tg1)
    {
        for (int tg2 = tg1 + 1; tg2 < N; ++tg2)
        {
            if (sum - (arr[tg1] + arr[tg2]) == TOTAL)
            {
                output(tg1, tg2);
                return 0;
            }
        }
    }
}

 

제출 코드 (Java)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[9];
		
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(sc.next());
		}
		Arrays.sort(arr);
		int result = 0;
		int no1 = 0, no2 = 0;
		outer:
		for (int i = 0; i < arr.length-1; i++) {
			int end = arr.length-1;
			
			while(true){
				if(i == end)
					break;
				int sum = 0;
				for(int j=0; j < arr.length; j++){
					if(j != i && j != end){
						sum += arr[j];
					}
				}
				if(sum == 100){
					no1 = i;
					no2 = end;
					break outer;
				}
				end--;
			}
		}
		
		for (int i = 0; i < arr.length; i++) {
			if(i != no1 && i != no2){
				System.out.println(arr[i]);
			}
		}
	}
}