백준 5557. 1학년

🅰 백준 5557. 1학년

5557번: 1학년

✏️ 문제 풀이

• 2차원 배열을 이용해서 각 수식을 순서대로 +, - 해서 dp[][] index에 저장한다.
• 행은 각 수식의 수만큼 만들고 계산되는 수식은 0~20 사이에 있기 때문에 열은 0~20으로 생성한다.
• dp[N+1][21]
• 계산해서 나오는 값들은 index로 표현할 수 있기 때문에 각 숫자마다 +연산을 한 값이 20보다 작거나 같으면      dp[i][j+number[i]] += dp[i-1][j], -연산을 한 값이 0보다 크거나 같으면 dp[i][j-number[i]] -= dp[i-1][j]가 된다.
• 이전 값을 계속해서 더해주는 이유는 연산을 하다보면 8이라는 숫자가 2번 3번 중복되서 나올 수 있기 때문에 이전값을 계속해서 더해주면 마지막에 나오는 수를 index로 하여 검색을 하면 dp[N-1][number[N]] 에 저장된 값이 마지막에 나오는 수가 되기위해 계산할 수 있는 등식의 수가 된다.

✏️ 소스코드

package dp;

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

public class Main_골드5_5557_1학년 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int number[] = new int[N + 1];
		long dp[][] = new long[N + 1][21];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; i++) {
			number[i] = Integer.parseInt(st.nextToken());
		}
		dp[1][number[1]] = 1;
		for (int i = 2; i < N; i++) {
			for (int j = 0; j <= 20; j++) {
				if (dp[i - 1][j] == 0)
					continue;
				int plusInput = j + number[i];
				int minusInput = j - number[i];
				if (minusInput >= 0) {
					dp[i][minusInput] += dp[i - 1][j];
				}
				if (plusInput <= 20) {
					dp[i][plusInput] += dp[i - 1][j];
				}
			}
		}
		System.out.println(dp[N-1][number[N]]);
	}
}

 

✅ 후기

• 2차원 배열로 접근하는 비슷한 문제라 쉽게 생각할 수 있었다. dp는 많이 풀면 풀수록 익숙해지는 유형인 것 같다.