<링크>
https://www.acmicpc.net/problem/6603
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include<stdio.h> #include<vector> using namespace std; vector<int> num(13); vector<int> v; int N; void dfs(int, int); int main() { while (1) { scanf("%d", &N); if (N == 0) break; for (int i = 1; i <= N; ++i) scanf("%d", &num[i]); dfs(1, 0); printf("\n"); } } void dfs(int i, int len) { if (len == 6) { for (int i = 0; i < 6; ++i) printf("%d ", v[i]); printf("\n"); return; } if (i > N) return; v.push_back(num[i]); dfs(i+1, len + 1); v.pop_back(); dfs(i+1, len); } | cs |
<풀이>
조합을 만들 때는
num[i]를 조합에 넣는다, 안넣는다로 따진다.
순열처럼 for문을 쓰지 않고 재귀를 돌려도 된다.
1 2 3 4 5 6 7 8 9 10 11 12 | void dfs(int i, int len) { if (len <= ?) { ; } if (i > N) return; v.push_back(num[i]); dfs(i+1, len + 1); v.pop_back(); dfs(i+1, len); } | cs |
이렇게 하면 len의 조건을 수정해서 좀 더 유연하게 쓸 수 있다.
로또같은 경우는 len==6일때 출력하는 방식이었다.
위코드에서 기저점을 len<=3 으로 바꾸면,
길이가 3 이하인 조합을 중복없이 알아낼 수 있다.
예를들어
<N=6, num={1,2,3,4,5,6}>
len=3이하일때 만들수있는 조합
1
1 2
1 2 3
1 2 4
1 2 5
1 2 6
1 3
1 3 4
1 3 5
1 3 6
1 4
1 4 5
1 4 6
1 5
1 5 6
1 6
2
2 3
2 3 4
...
위와같은 조합들로 처리하고싶을 때 편리하다.
관련문제 : 백준 15686 치킨배달
https://www.acmicpc.net/problem/15686
넣는다, 안넣는다 방식으로 재귀호출하면
i가 한도끝도없이 이어지게되므로 i가 N을 초과하면 리턴해줘야한다.
'알고리즘 풀이 > DFS' 카테고리의 다른 글
| 백준 10971 외판원 순회 2 (0) | 2018.07.28 |
|---|---|
| 백준 10819 차이를 최대로 (0) | 2018.07.27 |
| 백준 10974 모든 순열 (2) | 2018.07.24 |
| KOITP 큰수만들기 (0) | 2018.07.23 |
| 백준 11724 연결 요소의 개수 :: 들짐승 (0) | 2018.07.23 |
