[백준] 2309 일곱난쟁이

1. 문제

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

2. 접근방법

조합을 이용하는 아주 기본적인 문제

 

9명의 난쟁이 중 7명의 난쟁이를 뽑아 그 합이 100이 되는 경우를 찾으면 된다.

 

9 C 7 의 문제

 

3. 풀이

1. 난쟁이들 배열에 넣어두고

2. 9명 중 7명 뽑는 경우를 모두 구하고

3. 그 중 합이 100이 되는 경우를 찾으면

4. 그 때의 난쟁이들을 sort해서 출력

4. 자바 코드

package Bronze;

import java.util.Arrays;
import java.util.Scanner;

public class P2309일곱난쟁이 {
	static int N = 9;
	static int nangen[] = new int[N];
	static int R = 7;
	static int sel[] = new int[R];
	static int h_idx[];

	static void Search(int idx, int s_idx) {
		if (s_idx == R) {
			int sum = 0;
			for (int i = 0; i < R; i++)
				sum += sel[i];
			if (sum == 100) {
				h_idx = (int[])sel.clone();
			}

			return;
		}
		if(idx == N)
			return;
		
		sel[s_idx] = nangen[idx];
		Search(idx+1, s_idx+1);
		Search(idx+1, s_idx);

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		for (int i = 0; i < N; i++)
			nangen[i] = sc.nextInt();
		
		
		Search(0,0);
		Arrays.sort(h_idx);
		for(int i : h_idx)
			System.out.println(i);
		

	}

}

5. 마치며

아주 기본적인 조합을 이용해보는 문제였다.