글 읽기 - 고수님들. 도와주세요!

bitstr58 3년 전 0

안녕하세요. 먼저 감사드립니다.

부분수열을 구하는거니까 현재 인덱스의 수를 '선택한다' '선택 안 한다' 두 가지로 재귀 호출을 했습니다.

index가 초과 나는것을 걸러냈는데도 틀리는데요. 어느 부분이 모자란지 도움을 구하고자 글 올립니다.

감사합니다.

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


int N, S, cnt;
int a[21];

void dfs(int index, int sum){
	
	if(index >= N) return;
	
	if(sum == S){
		cnt++;
		return;
	}

	dfs(index+1, sum+a[index]); // 포함한다.
	dfs(index+1, sum); // 포함 안한다  
} 

int main(void){

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

	dfs(0, 0);
	
	cout << cnt;

	return 0;
} 

hae 3년 전 1

1. index >= N 이 먼저 나와서 마지막 인덱스까지 포함한 sum 은 체크못하고 종료됩니당

2. S가 0일 경우 처음 sum도 0 이기 때문에 계속 포함 안하게 되면 정답으로 한번 추가됩니당

bitstr58 3년 전 0

@hae 님 감사합니다!!!

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

문제

문제

출처

ICPC

고수님들. 도와주세요!

bitstr58 3년 전 0

hae 3년 전 1

bitstr58 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말