[BOJ] 5557 1학년 - JAVA

1. 문제

5557번: 1학년

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

---

2. 풀이

long타입 2차원배열 dp를 만든다. dp[i][j]는 i번째 숫자를 가지고 결과 j(0<=j<=20)를 만든 경우의 수다. 
첫 번째 숫자는 연산 없이 고정이라 dp[0][첫번째숫자]에 1을 저장하고 시작한다.
dp를 채울 때 순서대로 연산해야하기 때문에 가장 바깥 반복문은 숫자의 인덱스만큼 탐색한다. 단, 가장 마지막 숫자는 탐색할 필요 없다.(등호사용하기 때문)
idx마다 0부터 20까지 탐색하는데, 이 수는 이전idx에서 나온 결과들이라고 보면 된다.
만약 dp[idx-1][num]==0이라면 이전 idx에서 만들어지지 않았다는 의미이므로 다음 수로 넘어간다.
num+현재숫자가 0이상 20이하일때 dp[idx][새 숫자]에 이전idx결과 경우의 수를 더한다.
 
dp를 다 채웠다면 답을 출력해야한다.
dp[마지막에서 두번째 숫자idx][가장 마지막 숫자]는 마지막에서 두번째 숫자에서 가장 마지막 숫자로 연산되는 경우의 수가 담겨있다.
dp[N-2][number[N-1]]을 출력한다.

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

public class BOJ_5557_1학년 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int[] number = new int[N];
		StringTokenizer st = new StringTokenizer(in.readLine());
		for(int i=0;i<N;i++) number[i] = Integer.parseInt(st.nextToken());

		long[][] dp = new long[N][21];
		dp[0][number[0]] = 1;
		for(int idx=1;idx<N-1;idx++){
			for(int num=0;num<21;num++){//이전값
				if(dp[idx-1][num]==0) continue;
				if(num+number[idx] < 21) dp[idx][num+number[idx]] += dp[idx-1][num];
				if(num-number[idx] > -1) dp[idx][num-number[idx]] += dp[idx-1][num];
			}
		}

		System.out.println(dp[N-2][number[N-1]]);
	}
}

---

3. 결과

재귀로 푸려다가 너무 오래 시간이 걸리는 걸 보고 빠르게 접었다.
역시 이렇게 숫자가 큰 건 의심하고 봐야한다.