๋ ์ผ ๋ก๋๋ {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์ด ํ๋ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค ์๋ฅผ ๊ณ ๋ฅด๋ ๋ชจ๋ ๋ฐฉ๋ฒ์ ์ถ๋ ฅํ๋ค. ์ด๋, ์ฌ์ ์์ผ๋ก ์ถ๋ ฅํ๋ค.
๊ฐ ํ ์คํธ ์ผ์ด์ค ์ฌ์ด์๋ ๋น ์ค์ ํ๋ ์ถ๋ ฅํ๋ค.
K๊ฐ์ ์๋ก ๋ค๋ฅธ ์ซ์๋ก 6์๋ฆฌ์ ๋ก๋๋ฒํธ๋ฅผ ๋ง๋ค์ด์ผํจ
๊ฐ๋ฅํ ๋ก๋ ๋ฒํธ ๋ชจ๋ ์ถ๋ ฅ
์กฐํฉ์ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ๊ตฌํ๊ธฐ :
์ฌ๊ทํจ์๋ฅผ ์ด์ฉํ์ฌ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ (dfs)
1) ์ฌ๊ทํจ์๋ฅผ ์ด์ฉํ์ฌ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์
result[i] = true;
dfs(depth+1, i+1);
result[i] = false;
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;
}
}
}
์ฑ๊ณต~