[BaekJoon] 5557 1학년 (Java)

1.  문제 링크

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

2.  문제

요약

• 숫자가 줄 지어있는 것들에서 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에 '+' 또는 '-'를 넣어 등식을 만듭니다.
• 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하인 올바른 등식을 만드려고 합니다.
• 숫자가 주어졌을 때, 만들 수 있는 올바른 등식의 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 100보다 작거나 같은 숫자의 개수 N이 주어지고 두 번째 줄에 0보다 크거나 같고 9보다 작거나 같은 정수인 N개의 정수가 주어집니다.
• 출력: 첫 번째 줄에 만들 수 있는 올바른 등식의 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	static int[] nums;
	static long[][] dp;
	static int result, count = 0;
	public long findCaseNum(int index, int total) {
		if(total < 0 || total > 20) {
			return 0;
		}
		if(index == nums.length - 2) {
			return (total == nums[nums.length - 1]) ? 1 : 0;
		}
		if(dp[total][index] != -1) {
			return dp[total][index];
		}
		dp[total][index] = 0;
		return dp[total][index] += findCaseNum(index + 1, total + nums[index + 1]) + findCaseNum(index + 1, total - nums[index + 1]);
	}
	
	public long getCaseNum() {
		dp = new long[21][100];
		for(int i = 0; i < 21; i++) {
			Arrays.fill(dp[i], -1);
		}
		return findCaseNum(0, nums[0]);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		String[] input = br.readLine().split(" ");
		br.close();
		nums = new int[num];
		for(int i = 0; i < num; i++) {
			nums[i] = Integer.parseInt(input[i]);
		}
		Main m = new Main();
		bw.write(m.getCaseNum() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• 계산 중간에 0보다 작거나 20보다 큰 수가 나오면 해당 식으로는 올바른 등식을 만들 수 없으며 (N - 1)번째까지의 식의 결과가 N번째 수와 같아야 합니다.
• 이 조건들을 지키며 메모이제이션을 진행합니다.
• 지금까지의 결과에 다음 수를 더한 경우와 다음 수를 뺀 경우를 각각 재귀함수를 통해 구하는데
  • 만약 해당 결과가 0보다 작거나 20보다 크면 해당 식으로는 올바른 등식을 만들 수 없기 때문에 0을 반환하고
  • (N - 1)번째까지의 수까지 계산이 되었다면, 해당 결과가 N번째 수와 같을 때는 1을 그렇지 않을 때는 0을 반환하며
  • 이미 현재까지 계산된 마지막 수에서 지금까지 계산된 값이 이전에 이미 만들어져서 만들어지는 등식의 개수를 알고 있다면, 해당 값을 이용하기 위해 해당 값을 반환합니다.

public long findCaseNum(int index, int total) {
	if(total < 0 || total > 20) {
		return 0;
	}
	if(index == nums.length - 2) {
		return (total == nums[nums.length - 1]) ? 1 : 0;
	}
	if(dp[total][index] != -1) {
		return dp[total][index];
	}
	dp[total][index] = 0;
	return dp[total][index] += findCaseNum(index + 1, total + nums[index + 1]) + findCaseNum(index + 1, total - nums[index + 1]);
}

1. 주어진 수들을 배열 nums에 담습니다.
2. 주어지는 수의 최대 개수가 100이고 계산되어 나올 수 있는 수가 0 이상 20 이하이기 때문에 행의 길이가 21이고 열의 길이가 100인 2차원 배열 dp를 생성하고 배열 dp의 모든 값을 -1로 초기화합니다.
3. 1번째 수부터 재귀함수를 통해 식을 만들어가며 만들 수 있는 올바른 등식의 개수를 구합니다. 재귀함수에는 매개변수로 계산할 숫자의 위치를 나타내는 index와 지금까지의 수를 계산한 값인 total을 갖습니다.
   1. total이 0보다 작거나 20보다 크다면 계산되어 나올 수 있는 수가 0 이상 20 이하라는 조건이 만족되지 못하므로 0을 반환합니다.
   2. index가 (N - 2)라면, 즉 (N - 1)번째 수까지 계산되었다면, 그 때의 total 값이 N번째 수와 같다면 1을 반환하고 그렇지 않다면 0을 반환합니다.
   3. 만약 dp[total][index]의 값이 -1이 아니라면, 즉 이미 방문되어 몇 개의 등식이 만들어지는지 계산되었다면 해당 값을 반환합니다.
   4. 위 경우 모두 아니라면 dp[total][index]의 값을 0으로 설정하고 재귀함수를 통해 total에 다음 수를 더한 경우와 total에 다음 수를 뺀 경우를 계산하고 각 경우에서 계산된 올바른 등식의 개수를 더하여 dp[total][index]에 더해줍니다.