https://www.acmicpc.net/problem/1182
풀이
부분집합의 합을 구하여 입력된 S와 같은 부분집합의 개수를 출력하는 문제이다.
여기서 내가 생각하는 중요한 점은 두 가지이다.
1. 부분집합을 구하는 방법
2. 부분집합을 구하는 중간에 S와 같다고 개수를 카운트하면 안 된다는 것이다.
설명
부분집합을 구하는 방법은 아래 그림과 같이 그래프를 그려 표현할 수 있다.
그림은 이상하지만...위의 그림처럼 입력된 배열의 값들을 사용할지 안 할지를 구분해가면서 트리의 끝에 가서 부분집합의 합을 구하여야 된다는 것이다.
마지막에 부분집합의 구해야되는 이유는 만약 N이 5, S가 3이며 입력되는 수들이 1 1 2 -1 1을 예로들면
N=5, S=3, arr[5]={1,1,2,-1,1}
3=arr[0]+arr[2]=arr[1]+arr[2]가 답이라 여기서 카운트를 해버리면 틀리게된다.
그 이뉴는 3=arr[0]+arr[2]+arr[3]+arr[4]=arr[1]+arr[2]+arr[3]+arr[4]도 답이기 때문에 트리의 끝까지 가서 집합의 합을 구하여야 된다는 것이다.
아래는 N=5, S=3, arr[5]={1,1,2,-1,1}의 예이다. 부분집합들의 합이 3인 집합들을 출력한 것이다.
제출한 코드
처음 제출한 코드에서 num++해준 코드에 반복문과 조건문을 사용하면 위의 사진과 같이
조건을 만족하는 부분집합을들 출력할 수 있다.
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | //처음 답안으로 제출한 코드 #include <stdio.h> int N, S, arr[20], num,visit[20],k; void check(int n) { int total = 0; int flag = 0; if (n == N) { for (int i = 0; i < n; i++) { if (visit[i]) { flag = 1; total += arr[i]; } } if (total == S&&flag==1) { num++; } return; } visit[n] = 1; check(n + 1); visit[n] = 0; check(n + 1); } int main() { scanf("%d %d",&N, &S); for (int i = 0; i < N; i++) scanf("%d",&arr[i]); check(0); printf("%d",num); return 0; } //수정하여 제출한 코드 #include <stdio.h> int N, S, arr[20], num; void check(int n,int total) { if (n > N) return; if (n == N&&total==S) { num++; return; } check(n + 1,total+arr[n]); check(n + 1,total); } int main() { scanf("%d %d",&N, &S); for (int i = 0; i < N; i++) scanf("%d",&arr[i]); check(0,0); if (S == 0) num--; //S가0이면 공집합도 해로 카운트해서 정답에서 -1을 해주었다. printf("%d",num); return 0; } | cs |
'SW 업무 관련 > 백준' 카테고리의 다른 글
[BAEKJOON] 1697_숨바꼭질_C언어 (418) | 2017.08.01 |
---|---|
[BAEKJOON] 9934_완전 이진 트리_C언어 (2) | 2017.08.01 |
[BAEKJOON] 11723_집한_C언어 (0) | 2017.07.25 |
[BAEKJOON] 10971_외판원 순회 2_C언어 (0) | 2017.07.23 |
[BAEKJOON] 1406_에디터_C언어 (0) | 2017.07.17 |