백준 5557번: 1학년

문제 설명

• https://www.acmicpc.net/problem/5557
• N-1개의 숫자를 적절히 더하거나 빼 N번째 숫자를 만들어야 합니다.
  계산은 왼쪽부터 실행되고 중간계산과정에서 0~20이외의 숫자가 나오면 안됩니다.

접근법

• 했던 생각

  1. dp[i]를 i번째 원소까지 고려했을 때 올바른 등식의 개수라고 정의하니 dp[i]와 dp[i+1]의 관계를 유추할 수 없었습니다.
  2. 모든 연산을 실행하기에는 2^100이라는 큰 연산횟수가 필요했습니다.

• 모든 연산의 결과값이 0~20사이의 숫자이기 때문에 dp를 숫자 i까지 고려했을 때의 연산결과로 정의하고 2차원 배열로 설정했습니다.
  dp[i][j]는 j번째 값까지 고려했을 때 연산결과로 i가 몇개인지 입니다.

  • dp[i-num][j] += dp[i][j-1]
  • dp[i+num][j] += dp[i][j-1]

정답

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[N];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		long[][] dp = new long[21][N];
		dp[arr[0]][0] = 1;
		for (int i = 1; i < N-1; i++) {
			int num = arr[i];
			for (int j = 0; j <= 20; j++) {
				if(dp[j][i-1] != 0) {
					if(0<= j-num) {
						dp[j-num][i] += dp[j][i-1];						
					}
					if(j+num <= 20) {						
						dp[j+num][i] += dp[j][i-1];
					}
				}
			}
		}
				
		System.out.println(dp[arr[N-1]][N-2]);
//		for (int i = 0; i < dp.length; i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
		

	}
}