[Algorithm] ๐Ÿ’ฐ๋ฐฑ์ค€ 6603 ๋กœ๋˜

0. ๋ฌธ์ œ

๋…์ผ ๋กœ๋˜๋Š” {1, 2, ..., 49}์—์„œ ์ˆ˜ 6๊ฐœ๋ฅผ ๊ณ ๋ฅธ๋‹ค.
๋กœ๋˜ ๋ฒˆํ˜ธ๋ฅผ ์„ ํƒํ•˜๋Š”๋ฐ ์‚ฌ์šฉ๋˜๋Š” ๊ฐ€์žฅ ์œ ๋ช…ํ•œ ์ „๋žต์€ 49๊ฐ€์ง€ ์ˆ˜ ์ค‘ k(k>6)๊ฐœ์˜ ์ˆ˜๋ฅผ ๊ณจ๋ผ ์ง‘ํ•ฉ S๋ฅผ ๋งŒ๋“  ๋‹ค์Œ ๊ทธ ์ˆ˜๋งŒ ๊ฐ€์ง€๊ณ  ๋ฒˆํ˜ธ๋ฅผ ์„ ํƒํ•˜๋Š” ๊ฒƒ์ด๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด, k=8, S={1,2,3,5,8,13,21,34}์ธ ๊ฒฝ์šฐ ์ด ์ง‘ํ•ฉ S์—์„œ ์ˆ˜๋ฅผ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋Š” ์ด 28๊ฐ€์ง€์ด๋‹ค. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
์ง‘ํ•ฉ S์™€ k๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ˆ˜๋ฅผ ๊ณ ๋ฅด๋Š” ๋ชจ๋“  ๋ฐฉ๋ฒ•์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ฒซ ๋ฒˆ์งธ ์ˆ˜๋Š” k (6 < k < 13)์ด๊ณ , ๋‹ค์Œ k๊ฐœ ์ˆ˜๋Š” ์ง‘ํ•ฉ S์— ํฌํ•จ๋˜๋Š” ์ˆ˜์ด๋‹ค. S์˜ ์›์†Œ๋Š” ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค.
์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰ ์ค„์—๋Š” 0์ด ํ•˜๋‚˜ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ
๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค ์ˆ˜๋ฅผ ๊ณ ๋ฅด๋Š” ๋ชจ๋“  ๋ฐฉ๋ฒ•์„ ์ถœ๋ ฅํ•œ๋‹ค. ์ด๋•Œ, ์‚ฌ์ „ ์ˆœ์œผ๋กœ ์ถœ๋ ฅํ•œ๋‹ค.
๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค ์‚ฌ์ด์—๋Š” ๋นˆ ์ค„์„ ํ•˜๋‚˜ ์ถœ๋ ฅํ•œ๋‹ค.

1. ๋ฌธ์ œ ๊ฐ„๋‹จ ํ•ด์„

K๊ฐœ์˜ ์„œ๋กœ ๋‹ค๋ฅธ ์ˆซ์ž๋กœ 6์ž๋ฆฌ์˜ ๋กœ๋˜๋ฒˆํ˜ธ๋ฅผ ๋งŒ๋“ค์–ด์•ผํ•จ
๊ฐ€๋Šฅํ•œ ๋กœ๋˜ ๋ฒˆํ˜ธ ๋ชจ๋‘ ์ถœ๋ ฅ

2. ์•„์ด๋””์–ด

์กฐํ•ฉ์˜ ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ๊ตฌํ•˜๊ธฐ : kC6kC_6

3. ํ•ต์‹ฌ ํ’€์ด

1) ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ํƒ์ƒ‰

result[i] = true;
dfs(depth+1, i+1);
result[i] = false;

4. ์ฝ”๋“œ

import java.util.*;
public class BOJ_6603 {
	static int count = 0;
	static int k;
	static int arr[]; 
	static boolean result[];
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			k = sc.nextInt();
			
			if(k == 0)
				break;
			
			arr = new int[k];
			result = new boolean[k];
			
			for(int i=0; i<k; i++)
				arr[i] = sc.nextInt();
			
			dfs(0, 0);
			System.out.println();
		}
		
	}

	public static void dfs(int depth, int start) {
		if(depth == 6) {
			for(int i=0; i<k; i++) {
				if(result[i])
					System.out.print(arr[i]+" ");
			}
			System.out.println();
			return;
		}
		
		for(int i=start; i<k; i++) {
			result[i] = true;
			dfs(depth+1, i+1);
			result[i] = false;
		}
		
	}
}

5. ๊ฒฐ๊ณผ


์„ฑ๊ณต~

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ