글 읽기 - 이문제는 제가 짠 코드에서 시간초과가 나네용.. 이렇게 접근하면 안돼는것인가요?

hik3562 4년 전 0

저는 단순하게

주어진 범위안에서 더한 값이 찾고자 하는 골 이라면

ans 값을 늘렸습니다. 다만,

반복문을 구성해서 callback 했는데 이렇게 하면 안돼는건가요?

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


public class Main {

	private static int a,b;
	private static int[] arr ;
	private static int ans;
	private static void dfs(int nn, int go) {
		if(nn>=a)
			return ;
		if(go==b) {
				ans +=1;
			
			return ;
		}
		else {
			for(int i=0; i<a; i++) {
				dfs(nn+1, go+arr[i]);
			}
		}
	}
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		arr = new int[a];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<a; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		dfs(0, 0);
		
		System.out.println(ans);
	}

}

chogahui05 4년 전 1

어떻게 짜신 것인지 모르겠지만.

예를 들어서 1번째 원소를 뽑거나 안 뽑거나를 선택했다고 했을 때.

다시 0번째 원소부터 선택하거나 안 할 필요가 있을까요? 풀이는 맞는데. 구현이 이상하네요. 다시 작성해 보세요.

djm03178 4년 전 1

질문을 올릴 때는 반드시 제출했던 코드 그대로를 한 자도 다름없이 올려주시기 바랍니다. 이 코드에는 package도 남아있고 메인 클래스의 이름도 Main이 아니기 때문에 제출했을 때 시간 초과가 아니라 컴파일 에러가 납니다.

hik3562 4년 전 0

@chogahui05 다시 생각해보니 파워셋의 개념으로 접근해야 할것 같습니다.. 0번째 원소를 다시 선택했던 이유는 순열 로 생각해서 접근했던것인데..

@djm03178 앗... ㅠㅠ 매번 죄송합니다. 유념하겠습니다.

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

문제

문제

출처

ICPC

이문제는 제가 짠 코드에서 시간초과가 나네용.. 이렇게 접근하면 안돼는것인가요?

hik3562 4년 전 0

chogahui05 4년 전 1

djm03178 4년 전 1

hik3562 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말