글 읽기 - 30%에서 계속 틀렸다고 뜹니다.. 반례좀 찾아주세요..!

jiwon0297 2년 전 0

dp로 다시 짜서 해결은 했는데 원래 했던 코드는 왜 안되는지 모르겠네요 ㅠㅠ

게시판에 있는 반례도 모두 돌려봤습니다..!

dfs로 부분집합으로 만들수있는 sum에 대해 체크해줬고, 추가 왼쪽에 올라갈때는 37줄에서 해줬습니다...

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N,M;
	static int[] choo;
	static boolean[] ok, visited;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); //추의 개수
		choo=new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int total=0;
		for(int i=0; i<N; i++) {
			choo[i] = Integer.parseInt(st.nextToken()); //추의 무게 
			total+=choo[i];
		}
		
		visited=new boolean[N];
		ok=new boolean[total+1]; //확인할 수 있는지 t/f 담을 배열
		dfs(0,0); //만들 수 있는 무게인 ok 배열 구현
		
		StringBuilder sb = new StringBuilder();
		M = Integer.parseInt(br.readLine()); //구슬 개수
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int weight = Integer.parseInt(st.nextToken()); //구슬 무게
			if(weight>total) {sb.append("N "); continue;} //무게가 total보다 크면 무조건 N
			if(ok[weight]) sb.append("Y "); //true면 Y
			else { //false 일 때 
				boolean flag = false;
				for(int j=0; j<N; j++) {
					if(weight+choo[j]<=total && ok[weight+choo[j]]) {
						flag=true; //구슬과 choo와 더한 값이 true면(가능하다면) Y
						break;
					}
				}
				if(flag) sb.append("Y ");
				else sb.append("N "); //아니면 N
			}
		}
		
		System.out.println(sb.toString()); //결과 출력 
	}

	private static void dfs(int cnt, int sum) {		
		//이미 chk 되어있으면 넘기기
		if(ok[sum]) return ;
		ok[sum]=true;
		
		//개수가 N넘어가면 넘기기
		if(cnt>=N) return ;
		
		//부분집합 구하기 (추로 만들 수 있는 무게)
		for(int i=0; i<N; i++) {
			if(visited[i]) continue;
			visited[i]=true;
			sum+=choo[i];
			dfs(cnt+1, sum);
			sum-=choo[i];
			visited[i]=false;
		}
	}
}

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

문제

문제

출처

ICPC

30%에서 계속 틀렸다고 뜹니다.. 반례좀 찾아주세요..!

jiwon0297 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말