[백준 5557번] 1학년 - java

문제 설명

1. N개의 숫자가 주어진다.

2. 맨 뒤의 숫자는 결과값이며, +와 -를 사용해가면서 숫자를 만든다.

3. 만들어지는 숫자는 0~20사이의 정수이다.

4. 마지막의 결과값을 만들 수 있는 경우의 수를 구하면 된다.

 

풀이 과정

 1. 처음에는 완전탐색을 사용해야 하는 문제라고 생각했는데, 이거 완탐으로 절대 못푼다. 시간초과가 엄청 날것이다.

 2. DP를 사용해서 진행한다. 순서는 아래와 같다.

A DP는 이중 배열을 사용하여 [해당process숫자][만들어지는수사] = 가능한 경우의 수 를 저장하도록 한다.

B 맨 처음 숫자는 당연히 [0][첫번째입력숫자] = 1일 것이다.

C 나는 DP와 완전탐색을 약간 합친 방법을 통해 구현하였는데, 다음번의 경우를 구하려면 이전의 DP에서 만들어진 경우의 수가 존재하면, 그 경우의 수에서 해당 숫자로 도달 가능한지 판별하여 있는 경우 더해주었다.

D 모든 경우를 구해준 후, 마지막 숫자에 관한 DP를 확인해주면 된다. -> 이 마지막 DP는 N개의 숫자에 대해 진행한 덧셈/뺄셈의 process이기 때문에 N-1이고 0부터 시작해서 N-2이다. 

 3. 아마 이중for문 대신에 조립하는 식으로 진행하면 시간복잡도에서 유리하게 해결할 수 있을 것 같기는 한데...나는 이게 더 편해서 이렇게 했다.

코드

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int num[] = new int[N];
	for(int i=0; i<N; i++) num[i] = sc.nextInt();
	long dp[][] = new long[N][21];
	dp[0][num[0]] = 1;
	for(int i=1; i<N-1; i++){
	for(int j=0; j<21; j++){
	if(dp[i-1][j]==0) continue;
	int plus = num[i] + j;
	int minus = j - num[i];
	if(plus>=0 && plus<=20){
	dp[i][plus] += dp[i-1][j];
	}
	if(minus>=0 && minus<=20){
	dp[i][minus] += dp[i-1][j];
	}
	}
	}
	System.out.println(dp[N-2][num[N-1]]);
	}
	}

view raw 1학년.java hosted with ❤ by GitHub