글 읽기 - 부분수열 완전탐색 문제 도와주시면 감사하겠습니다.ㅠㅠ

coramdeo0708 4년 전 0

나름 다양한 입력 사례를 넣었는데도 문제를 발견하지 못했습니다.. 도와주시면 감사하겠습니다.

#include <iostream>
#include <vector>

using namespace std;

#define FOR(i, n) for (int i = 0; i < n; i++)
#define INF (987654321)
int N, S;
vector<int> numArr;

bool initFlag = true;

int segSum(int start, int sum) {
    if (sum == S && !initFlag) return 1;
    if (start >= N) return 0;

    initFlag = false;

    int ret = 0;
    for (int next = start; next < N; ++next) {
        sum += numArr[next];
        ret += segSum(next + 1, sum);
        sum -= numArr[next];
    }
    return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> S;

    numArr.resize(N);
    FOR(i, N) {
        cin >> numArr[i];
    }

    cout << segSum(0, 0) << "\n";

    return 0;
}

sait2000 4년 전 0

14번 줄이 이상하네요. 뒤쪽에 합이 0이 되도록 더 붙일 수도 있을 것 같은데

coramdeo0708 4년 전 0

댓글 감사합니다! 제가 말씀하신 부분을 잘 이해하지 못했어요.. 저 부분은 제가 cout << segSum(0,0) 부분에서 처음에 sum을 0으로 초기화해서 넣는데, S가 0일 때는 바로 빠져나와 버려서, 가장 처음 sum은 답으로 생각하지 않기 위해 걸어 놓은 플래그 입니다.

renkousami 4년 전 1

2 0

0 0

같은 경우 3이 나와야 하지 않을까요

coramdeo0708 4년 전 0

아하 그 경우가 있네요. 감사합니다 수정 해보겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

부분수열 완전탐색 문제 도와주시면 감사하겠습니다.ㅠㅠ

coramdeo0708 4년 전 0

sait2000 4년 전 0

coramdeo0708 4년 전 0

renkousami 4년 전 1

coramdeo0708 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말