[백준 5557] 1학년 -JAVA // le_effort//

사용 알고리즘 : DP

 

문제 좀 꼼꼼히 읽자!!!!

 

문제에 힌트가 다 있는데 문제를 대충 읽어서 삽질했다.

 

중간에 나오는 수가 모두 0 이상 20 이하 여야 한다.라는 조건이 떡하니 쓰여 있는데

최종 결괏값만 음수가 아니면 되나 라고 삽질을 했다

 

DP 배열은 이렇게 설정한다

DP [i][j]

i : i번째 수까지 이용했을 때

j : 0~20 번째 수를 만들 수 있는가?

 

설정할 때 DP의 크기는 DP [n][21] 크기로 만든다

 

dp[1][arr[1]]=1;
        
        for(int i=2; i<n; i++) {
            for(int j=0; j<=20; 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];
                    }
                }
            }
        }

 

핵심 코드다

 

예제 입력 케이스에서

 

11

8 3 2 4 8 7 2 4 0 8 8

 

제일 첫 번째 수  8은 만들 수 있다

DP [1][8] = 1;

 

i 반복문은 2부터 시작해서

조건 if(DP [i-1][j])!=0

DP [1][j] 중 0 이 아닌 것은 DP [1][8]이다

 

즉 현재 j가 가리키는 값이 8이라는 것이다 

이제 여기서 j+arr [i] j-arr [i]를 해서 진행하면 된다

arr [2]가 3 일 때

j+arr [i] = 8+3

j- arr[i] = 5

 

수 0~20 사이의 범위 안에 다 들어오니

DP [i][j+arr [i]] = DP [2][11]       

DP [i][j-arr [i]]  = DP [2][5]

 

여기에 전 값을 더해주면 된다. (전 값은 DP [1][8])

 

왜 dp[i][j+arr[i]] ++가 아니라 dp[i][j+arr[i]]+=dp[i-1][j] 일 까? 라고 생각 할 수도 있는데

 

예를 들어보자

 

DP[5][1] = 2가지 방법으로 만들수있따

DP[5][3] = 5가지 방법으로 만들수 있다.

 

다음 단계의 arr[6] = 1일때

더하기 연산을 했을 때 DP[6][2] += DP[5][1]

뺄셈 연산을 했을 때 DP[6][2]+=DP[5][3]

 

이런식으로 진행된다고 이해되면 될것 같다.

           

전체 코드

 

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    static long dp[][];
    static int arr[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        String[] t = br.readLine().split(" ");
        
        dp = new long[n+1][21];
        arr = new int[n+1];
        
        for(int i=1; i<=n; i++) {
            arr[i]=  Integer.parseInt(t[i-1]);
        }
        dp[1][arr[1]]=1;
        
        for(int i=2; i<n; i++) {
            for(int j=0; j<=20; 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-1][arr[n]]);
        
    }
}