백준_5557 1학년(자바) / DP

시간 & 메모리 제한

문제

입력 & 출력

 

DP를 이용한 문제풀이

package com.Back;

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

public class Back_5557 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		//범위를 정해줬습니다 0~20까지
		//조건에 보면 2^63-1
		long[][] dp = new long[N-1][21];
		int[] arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		dp[0][arr[0]]=1;
		for (int i = 1; i < N-1; i++) {
			for (int j = 0; j < 21; j++) {
				if(dp[i-1][j]!=0) {
					if(j+arr[i]<=20) dp[i][j+arr[i]] +=dp[i-1][j];					
					if(j-arr[i]>=0) dp[i][j-arr[i]] +=dp[i-1][j];					
				}
			}
		}
		System.out.println(dp[N-2][arr[N-1]]);
	}

}

- 이 문제를 읽어보면 DP를 이용해서 풀라는 느낌이 강하게 듭니다.

 

- 일단 0부터 20까지 갯수를 제한 시켰다는 것에 큰 힌트가 있었음을 알 수 있습니다.

 

- 이 문제를 풀기 위해서 이차원 DP배열을 만들었습니다.

 

- 각 숫자를 더하고 빼는 과정을 통해서 그 값에 도달할 수 있는 방법의 수를 표시합니다.

- 이 문제를....... 오랫동안 틀렸습니다. 문제를 다시 읽어보니 값의 크기가 2^63 -1 이하라는 것이였습니다.

 

int로 만들면 2^31-1의 크기까지 만들 수 있습니다. 따라서 DP의 자료형은 long형을 사용해 줘야 합니다.