[BOJ] 2309. 일곱난쟁이

22 Jun 2019

Reading time ~1 minute

for문을 이용한 조합(nCr)

for문을 이용한 조합(nCr)

for문을 r번 중첩하여 n개중에 r개를 뽑는 경우의 수를 출력할 수 있다.

예제코드는 다음과 같다.

for문을 이용한 조합을 사용한 예제코드(4C3)

public class main {
	public static void main(String[] args) {
		char arr[]= {'A','B','C','D'};

		for(int i=0;i<arr.length;i++) {
			for(int j=i+1;j<arr.length;j++) {
				for(int k=j+1;k<arr.length;k++){
					System.out.print(arr[i]+" "+arr[j]+" "+arr[k]);
					System.out.println();
				}
			}
		}		
	}
}

for문을 이용한 조합을 사용한 일곱난쟁이 코드

http://boj.kr/2309

9명의 난쟁이 중 진짜 난쟁이 7명의 키의 합이 100일 때 일곱난쟁이를 찾아 그 키를 각각 출력하는 문제

9명 중에 7명을 고르는 모든 경우의 수 9C7번 합을 계산하여

합이 100일 때를 출력!(for문으로 구현하려면 for문이 7번 중첩되어 비효율적임)

더 효율적인 코드를 작성하기 위해 반대로 생각해보면

입력으로 주어진 9명의 키의 합은 항상 일정하므로 난쟁이가 아닌 2명을 고르는 경우인

9C2(=9C7)번 전체 합에서 고른 두명의 키만 빼주어 계산한다.

(for문으로 구현하려면 for문이 2번만 중첩되서 더욱 효율적임)

http://codeplus.codes/f7443f083b8949d7a9cdcdbb411034aa

재귀를 이용한 조합을 사용한 일곱난쟁이 코드

재귀를 사용하여 조합을 만들고 그 만들어진 조합을 arr2에 저장하여 합이 100이면 출력하는 코드

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

public class Main {
	static boolean c[]=new boolean [9];
	static boolean flag;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int arr[]=new int [9];
		int arr2[]=new int [7];
		for(int i=0;i<9;i++) {
			arr[i]=sc.nextInt();
		}
		Arrays.sort(arr);
		go(arr,arr2,0,0);
	}

	public static void go(int arr[],int arr2[],int index,int start) {
		if(flag) {
			return;
		}
		if(index==7) {
			int sum=0;
			for(int i=0;i<7;i++) {
				sum+=arr2[i];
			}
			if(sum==100) {
				flag=true;
				for(int i=0;i<7;i++) {
					System.out.println(arr2[i]);
				}
			}
			return;
		}

		for(int i=start;i<9;i++) {
			if(c[i]) continue;
			arr2[index]=arr[i];
			c[i]=true;
			go(arr,arr2,index+1,i+1);
			c[i]=false;
		}
	}
}