글 읽기 - 1208번 질문이요. 어디가 문제인지 모르겠네요. ㅠㅠ

daeinki 7년 전 0

부분집합으로 묶을 수 있는 모든 경우의 수를 구해서는 O(n^40)이라 넘 느려서

3중 for문을 이용해서 부분집합의 합을 구해보려고 하고 있습니다.

여러가지 test case를 만들어서 돌려보면 모두 맞게 출력하고 있네요.

혹시 아래 문제에서 fail이 되는 test case가 없을까요?

어디가 문제인지 모르겠네요. ㅜㅜ

#include <stdio.h>

#define DEBUG	0

int nS[41];
int N, S;

int abs(int value)
{
	return value < 0 ? value * -1 : value;
}

int main(void)
{
	scanf("%d %d", &N, &S);

	S = abs(S);

	for (int i = 0; i < N; i++) {
		scanf("%d", &nS[i]);
	}

	int result = 0, i1, i2, i3;

	for (i1 = N - 1; i1 >= 0; i1--) {
		for (i2 = 0; i2 <= i1; i2++) {
			int sum = 0;

			for (i3 = i2; i3 <= i1; i3++) {
				sum += nS[i3];
			}
#if DEBUG
			printf("%d ~ %d = %d\n", i2, i1, sum);
#endif
			if (sum == S)
				result++;
		}
	}

	printf("%d\n", result);

	return 0;
}

zlzmsrhak 7년 전 0

연속하지 않은 부분집합은 계산에 포함되지 않습니다.

반례입니다.

3 0

0 0 0

답: 7

daeinki 7년 전 0

답변 감사합니다.

그런데 이해가 안가는 부분이 있는에요,

3 0

0 0 0

인경우 연속하지 않은 부분집합을 제외하면 6아닌가요?

0, 0, 0, 00, 00, 000 이렇게요.

zlzmsrhak 7년 전 0

답은 연속하지 않은 부분집합도 포함하기 때문에 7입니다. 문제를 잘 읽어보세요.

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

문제

문제

출처

ICPC

1208번 질문이요. 어디가 문제인지 모르겠네요. ㅠㅠ

daeinki 7년 전 0

zlzmsrhak 7년 전 0

daeinki 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말