글 읽기 - 이거 어디가 틀렸을까요??(c++)

112224 5년 전 0

오름차순 정렬한 이후에 현재까지의 합이 정답보다 클 경우 가지치기를 해주었습니다.

근데 이 부분이 틀리더라구요 ㅠㅠ

왜 틀렸는지 알려주실 고수님 구합니다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int a[20];
int n, k;
int ans;
void dfs(int now, int val)
{
	if (val > k)                //요기 주석처리하면 정답.
		return;
	if (now == n)
	{
		if (val == k)
			ans++;
		return;
	}
	dfs(now + 1, val + a[now]);
	dfs(now + 1, val);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	sort(a, a+n);

	dfs(0, 0);
	if (k == 0)
		ans--;
	

	cout << ans << '\n';

}

djm03178 5년 전 2

k가 음수이면 중간에 더 커지더라도 뒤쪽을 봐야 합니다. 현재보다 뒤에 음수가 있어서 값이 더 작아질 수 있기 때문입니다.

112224 5년 전 0

아하 감사합니다! 기본적인 걸 생각 못하고 있었네요 ㅠㅠ

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

문제

문제

출처

ICPC

이거 어디가 틀렸을까요??(c++)

112224 5년 전 0

djm03178 5년 전 2

112224 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말