[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. ์์ด๋์ด
์กฐํฉ์ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ๊ตฌํ๊ธฐ :
์ฌ๊ทํจ์๋ฅผ ์ด์ฉํ์ฌ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ (dfs)
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. ๊ฒฐ๊ณผ
์ฑ๊ณต~
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐ฐ๋ฐฑ์ค 6603 ๋ก๋), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-6603-๋ก๋์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค