글 읽기 - 시간 초과 질문입니다

darkziny22 9년 전 0

처음에는 백트래킹 형태로 모든 경우에 대해 계산해서 시간초과가 났습니다

그래서 생각해보니 0은 더하거나 빼거나 상관없이 그대로 유지되기 때문에

입력시 0의 수를 기억하고, 계산시에는 0을 건너뛰어 계산 하고 나온 값에

2를 0의 갯수만큼 제곱한만큼을 곱해서 출력했는데도 약 46%에서 시간초과가 뜨네요..

해결 할 방법이 뭐가 있을까요...?

import java.util.Scanner;

public class Main {
	
	private static int arr[];
	private static int n = 0;
	private static int cnt = 0;
	private static long zero = 0;
	
	public static void main(String[] args){
		run();
	}
	public static void run(){
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		arr = new int[n];
		
		for(int i=0; i<n; i++){
			arr[i] = sc.nextInt();
			if(arr[i]==0) zero++;
		}
		
		zero = (long)(Math.pow(2, zero));
		
		
		process(0, 0);
		System.out.println(cnt * zero);
	}
	public static void process(long result, int pos){
		
		if(pos==n-1 && result==arr[n-1]){
			cnt++;
		}
		
		if(result<=20 && result>=0){
			if(pos<n){
				
				if(arr[pos]==0)	pos++;
				
				process(result+arr[pos], pos+1);
				process(result-arr[pos], pos+1);
			}
		}
	}
}

yukariko 9년 전 3

dp에 대해 아시나요?

이 문제는 dp로 쉽게 해결이 가능합니다.

dp의 개념에 대해선

https://www.acmicpc.net/wiki/%EC%95%8C%EA%B3%A0%EB...

이곳(통칭 신의 문서)에 나와있으니 읽어보세요.

이 문제에 대해서 설명해보자면

앞에서 + - + - 의 연산을 통해 pos가 4, result가 2라고 합시다.

또, - + - + 의 연산을 통해 pos가 4, result가 2가 나왔습니다.

이 두 경우에서, 각 각 pos 뒤의 나머지를 가지고 경우의 수를 구하면

두개의 답이 서로 다를까요?

정답은 no입니다.

앞에서 어떤 연산과정을 거쳤던 간에, pos와 result가 같다면, 뒷부분의 경우의 수는 언제나 같습니다.

이러한 성질을 이용해서 이미 지나쳤던 pos, result 가 있다면, 다시 재귀하지 말고 예전에 구했던 값을 그대로 리턴해주면 됩니다.

그러면 모든 경우의수를 직접 구하지 않아도 답을 얻을 수 있죠.

darkziny22 9년 전 0

백트래킹으로만 해야 되는 것으로 잘못 생각했네요

굳이 모든 경우를 다 판단 할 필요는 없는 문제였나봅니다

dp로 다시 한번 해봐야겠습니다

감사합니다!

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

문제

문제

출처

ICPC

시간 초과 질문입니다

darkziny22 9년 전 0

yukariko 9년 전 3

darkziny22 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말