-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
4번 문제만 계속 틀립니다.
23.08.07 00:27 작성 조회수 307
0
안녕하세요 선생님!
항상 좋은 강의 감사히 잘 듣고 있습니다.
이번 문제에서 제 코드로는 4번 문제가 계속 틀렸다고 나와서 선생님 코드 그대로 따라했는데도 4번 문제가 틀렸다고 되더라구요... 채점기 output이 잘못된건지 제가 짠 코드가 잘못된건지 확인 부탁드립니다...!
제 코드
#include <stdio.h> #include <cmath> int n; int a[11]; int b[100]; int c[1025]; int sum; int idx = 1; void DFS(int x) { if(x == n+1) { sum = 0; for(int i = 1; i <= n; i++) if(b[a[i]] == 1) sum += a[i]; c[idx++] = sum; } else { b[a[x]] = 1; DFS(x+1); b[a[x]] = 0; DFS(x+1); } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); DFS(1); for(int i = 1; i <= pow(2, n); i++) { int temp = c[i]; if(temp == 0) continue; for(int j = 1; j <= pow(2, n); j++) { if(i == j) continue; if(temp == c[j]) { printf("YES"); return 0; } } } printf("NO"); return 0; }
선생님 코드
#include <stdio.h>
int n;
int a[11];
int total = 0;
bool flag = false;
void DFS(int x, int sum)
{
if(sum > (total/2)) return;
if(flag) return;
if(x == n+1)
{
if(sum == (total/2))
{
flag = true;
}
}
else
{
DFS(x+1, sum+a[x]);
DFS(x+1, sum);
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
total += a[i];
}
DFS(1, 0);
if(flag)
printf("YES");
else
printf("NO");
return 0;
}
답변을 작성해보세요.
0
김태원
지식공유자2023.08.07
안녕하세요^^
님의 코드는 아래와 같은 입력을 YES로 출력합니다.
4
1 3 4 5
위 입력을 {1, 3, 4}라는 부분집합과 {3, 5}라는 부분집합이 합이 같다고 판단해서 YES를 출력합니다.
답은 NO가 나와야 합니다. {1, 3, 4}가 하나의 부분집합이면 반대편 부분집합은 1, 3, 4를 뺀 {5}인 부분집 합 이어야 합니다. 즉 전체집합을 두 개의 부분집합으로 나누는 것입니다. 동일원소가 양속 부분집합에 모두 사용되면 안됩니다.
제 코드는 아래 부분을 수정하면 됩니다. total / 2를 하다보면 소수점 이하가 절삭되는 경우가 있어 if 조건문이 참이 되는 경우도 있습니다. if(sum == (total - sum))으로 바꾸면 100점 나올겁니다. 예를 들면 total값이 15이고 sum 값이 7이면 if( 7 == 15/2) 가 참이 되어 버립니다.
if(x == n+1) { if(sum == (total/2)) //if(sum == (total - sum)) 으로 수정 { flag = true; } }
답변 1