5557. 1학년

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

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이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

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

 

입출력 조건

• 첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.
• 첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 2^63-1 이하이다.

 

LOGIC

1. 각 정수에 대해 + 또는 -를 선택하는 경우의 수 ⇒ 즉, 부분 집합을 이용한다.
2. N이 100일경우 경우의 수는 2^98이므로 시간초과를 고려해 DP 사용

 

이 문제는 + 또는 -를 사용한 부분 집합의 경우의 수에서 조건에 맞는 경우의 수를 구하는 문제이다.

static long cal(int sum, int idx) {
    if(idx == N-1) { //끝까지 계산한 경우
        return sum == last ? 1 : 0; //값이 맞으면 경우의 수 +1
    }

    int s = sum + arr.get(idx); //더할 경우
    int d = sum - arr.get(idx); //뺄 경우
    long cnt = 0; //경우의 수

    if(s < 21) {
        cnt += cal(s, idx + 1);
    }

    if(idx != 0 && d > -1) {
        cnt += cal(d, idx + 1);
    }

    return cnt;
}

 

하지만 부분 집합의 경우의 수는 2^n 이므로 시간단축을 위해 DP로 메모이제이션을 사용하여 풀어야한다.

...
//입력된 숫자 중 N-1개의 값들에 대한 기록
//만들 수 있는 숫자는 0~20이므로 21개의 계산 결과 기록
dp = new long[N-1][21];
...

static long cal(int sum, int idx) {
    if(idx == N-1) { //끝까지 계산한 경우
        return sum == last ? 1 : 0; //값이 맞으면 경우의 수 +1
    }

    if(dp[idx][sum] != -1) //이미 했던 경우의 수 일 경우 저장된 값 리턴
        return dp[idx][sum];

    int s = sum + arr.get(idx); //더할 경우
    int d = sum - arr.get(idx); //뺄 경우
    long cnt = 0; //경우의 수

    if(s < 21) {
        cnt += cal(s, idx + 1);
    }

    if(idx != 0 && d > -1) {
        cnt += cal(d, idx + 1);
    }

    return dp[idx][sum] = cnt;
}

 

위 로직에서 또 주의할 점은 첫 번째 수로 0이 나올 경우 - 연산 후 음수 값이 나오면 로직이 끝나므로 주의해야 한다.

// idx가 0이 아니고 뺀 경우의 수가 0 이상일 경우에만 진행
if(idx != 0 && d > -1) {
	cnt += cal(d, idx + 1);
}

---

CODE

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 백준 5557. 1학년 - 골드 5
 * @category DP
 */
public class Main {
	static int N, last;
	static ArrayList<Integer> arr;
	static long dp[][]; //메모이제이션

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		arr = new ArrayList<>();
		dp = new long[N-1][21];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N-1; i++) {
			int n = Integer.parseInt(st.nextToken());
			
			arr.add(n);
			Arrays.fill(dp[i], -1);
		}
		
		last = Integer.parseInt(st.nextToken());
		cal(0, 0);
		System.out.println(dp[0][0]);
	}

	static long cal(int sum, int idx) {
		if(idx == N-1) { //끝까지 계산한 경우
			return sum == last ? 1 : 0; //값이 맞으면 경우의 수 +1
		}
		
		if(dp[idx][sum] != -1) //이미 했던 경우의 수 일 경우 저장된 값 리턴
			return dp[idx][sum];
		
		int s = sum + arr.get(idx); //더할 경우
		int d = sum - arr.get(idx); //뺄 경우
		long cnt = 0; //경우의 수
		
		if(s < 21) {
			cnt += cal(s, idx + 1);
		}
		
		if(idx != 0 && d > -1) {
			cnt += cal(d, idx + 1);
		}
		
		return dp[idx][sum] = cnt;
	}
}