[백준 5557번] 1학년

문제 : https://www.acmicpc.net/problem/5557

 

 

 

실패 이유 -> DP에 대한 점화식을 잡지 못했다.

처음 문제풀이를 진행할 때, DFS를 생각했는데, 시간복잡도 : O(2^98)이므로 (3<= N <= 100) DFS를 활용하면 시간 초과가 날 것이다.

 

이후, DP를 활용해야하는 줄은 알았지만 풀이 방법이 떠오르지 않았다.

 

 

 

https://dingdingmin-back-end-developer.tistory.com/entry/%EB%B0%B1%EC%A4%80-5557%EC%9E%90%EB%B0%94-java-1%ED%95%99%EB%85%84

백준 5557[자바] java 1학년

 

해당 블로그를 참고하였다.

 

문제의 핵심이다.

연산한 피연산자의 개수는 최대 N-1 개이고, 문제에서 0이상 20이하의 숫자만 인식할 수 있으므로, 2차원 배열로 DP를 나타낸다.

이후, 초기 피연산자의 경우의 수를 DP에 1가지 경우의 수로 넣어준다.

 

배열을 순회하면서, N-1번째까지의 피연산자의 값을 기존 연산 결과값이 존재할 때, 더하거나 빼주면서 0이상 20이하의 연산 결과값을 만족한다면 이전 경우의 수를 더해준다.

 

long[][] dp = new long[N][21]; // [피연산자의 개수][나올 수 있는 연산 결과값]

// 구하고 하는 값
// dp[N-2][arr[N-1]

dp[0][arr[0]] = 1; // 초기 경우의 수를 1로 저장

int plus, minus;

for (int i = 1; i < N-1; i++) {

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

 

 

전체 코드이다.

 

package _250513;

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

/**
 *packageName    : _250513
 * fileName       : BOJ_G5_5557_1학년
 * author         : moongi
 * date           : 5/13/25
 * description    :
 */
 
public class BOJ_G5_5557_1학년 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		long[][] dp = new long[N][21];

		// 구하고 하는 값
		// dp[N-2][arr[N-1]

		dp[0][arr[0]] = 1; // 초기 경우의 수를 1로 저장

		int plus, minus;

		for (int i = 1; i < N-1; i++) {

			for (int j = 0; j <= 20; j++) {
				if (dp[i - 1][j] != 0) {
					plus = j + arr[i];
					minus = j - arr[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][arr[N - 1]]);

	}
}