-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
질문있습니다
21.07.06 15:50 작성 조회수 108
0
61번 문제를 다르게 풀었는데 오류가 발생했습니다.
주어진 문제를 예시로 들자면 (2,4,6,8) 4개의 배열을 늘려서 (2,4,6,8,-2,-4,-6,-8) 8개로 선언한 뒤 DFS 함수를 사용했는데 답이 틀렸습니다.
스스로 디버그를 거쳤지만 오류를 발견하지 못했는데 무엇이 문제인가요?ㅠㅠ
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
int cnt=0, n, m, a[22];
void DFS (int L, int sum){
if(L == n+n+1){
if(sum == m) cnt++;
}
else {
DFS(L+1,sum + a[L]);
DFS(L+1,sum);
}
}
int main() {
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1; i<= n+n; i++){
if(i <= n) scanf("%d",&a[i]);
else a[i] = -(a[i-n]);
}
DFS(1,0);
printf("%d",cnt);
return 0;
}
답변을 작성해보세요.
0
김태원
지식공유자2021.07.10
안녕하세요^^
전역변수로 n, m을 잡았으면 main 함수에서 지역변수 선언을 하면 안됩니다.
그리고 아래 코드처럼 해서 path를 출력해보면 중복해서 개수를 카운팅하는 것을 알 수 있을 겁니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
int cnt=0, n, m, a[22], path[20];
void DFS (int L, int sum){
if(L == n+n+1){
if(sum == m){
cnt++;
for(int i=1; i<L; i++) printf("%d ", path[i]);
printf("\n");
}
}
else {
path[L]=a[L];
DFS(L+1,sum + a[L]);
path[L]=0;
DFS(L+1,sum);
}
}
int main() {
freopen("input.txt", "rt", stdin);
//int n,m;
scanf("%d %d",&n,&m);
for(int i = 1; i<= n+n; i++){
if(i <= n) scanf("%d",&a[i]);
else a[i] = -(a[i-n]);
}
DFS(1,0);
printf("%d",cnt);
return 0;
}
답변 1