글 읽기 - 부분집합의 합 틀린 케이스가 궁금합니다.

quki 7년 전 0

모든 부분집합의 경우에 대해 구하는데 틀린 케이스를 못찾겠네요 ㅠㅠㅠ

Set을 이용해서 경로(부분집합의 원소들) check를 한 다음에, 합을 검사해서 합이 S가 되는 경우에 count하는 방식으로 짰습니다.

틀린 케이스를 도저히 못찾겠네요 ㅠㅠ

뭐가 문제일까요?

import java.util.HashSet;
import java.util.Scanner;

public class Main {
	static int S;
	static int cnt = 0;
	static void go(int[] a, HashSet<Integer> check, int currIdx){
		int sum = 0;
		for(int e: check){
			sum+=e;
		}
		
		if(sum == S){
			cnt++;
		}
		
		for(int next = currIdx+1; next<a.length; next++){
			
			check.add(a[next]);
			go(a, check, next);
			check.remove(a[next]);
		}
	
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		S = sc.nextInt();
		int a[] = new int[N];
		for(int i = 0; i<N;i++){
			a[i] = sc.nextInt();
		}
		HashSet<Integer> check = new HashSet<>();
		
		for(int i = 0; i<N; i++){
			check.add(a[i]);
			go(a, check, i);
			check.remove(a[i]);
		}
		
		System.out.println(cnt);
	}

}

ntopia 7년 전 0

데이터 체크하는 코드를 내보니

같은 수가 두 개 이상 주어지는 데이터가 있네요 ... ㅡㅡ;

일단 HashSet 대신 다른 자료구조로 바꿔서 해보세요.

데이터 수정해달라고 글을 써야겠네요.

quki 7년 전 0

감사합니다^^

같은 수가 주어지는 데이터가 있었군요.

ntopia 님 덕분에 시간 낭비를 줄일 수 있었네요!

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

문제

문제

출처

ICPC

부분집합의 합 틀린 케이스가 궁금합니다.

quki 7년 전 0

ntopia 7년 전 0

quki 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말