백준 2629번: 양팔저울

문제 설명

• https://www.acmicpc.net/problem/2629
• 주어진 추의 수를 이용해 정해진 수를 만들 수 있는지 판별하는 문제입니다.

접근법

• 입력으로 주어진 숫자들을 적당히 더하거나 빼거나 사용하지 않으면서 특정 숫자를 만들 수 있는지 판별하는 문제입니다.

• 모든 경우의 수를 판별하는 부분집합을 그냥 사용하면 O(3^30)으로 시간초과가 발생합니다.
  시간을 줄이는 방법은 중복된 시행을 줄이는 것입니다. 이때 중요한 건 단순히 만들어진 숫자만 같은게 아니라 뒤에 남은 확인해볼 추의 개수 및 종류까지 같아야 중복된 시행입니다.

  • v[depth][num]은 depth번째 시도를 통해 num이라는 숫자가 만들어졌다는 의미입니다. depth가 동일하기 때문에 뒤에 남은 추의 개수와 종류가 동일하기 때문에 depth와 num이 같으면 중복으로 인정할 수 있습니다.
    1+1-1과 1+0+0은 depth와 num이 모두 동일하기 때문에 중복입니다. 하지만 1+0, 1은 앞의 값과 depth가 다르기 때문에 다른 경우의 수 입니다.

• 이 문제는 빼기가 가능하기 때문에 음수를 잘 고려해줘야 합니다.

  아래 코드는 제가 문제풀이 초기에 설계한 틀린 코드(정확히는 시간초과가 발생하는) 입니다.

  public static void subSet(int depth, int N, int[] nums, boolean[][] v, int makedNum, boolean[] dp) {
      if(makedNum >= 0) {
          dp[makedNum] = true;
          if(v[depth][makedNum]) return;
          v[depth][makedNum] = true;	
      }
  
      if(depth == N || makedNum > 15000) {
          return;
      }
  
      subSet(depth+1,N,nums,v,makedNum+nums[depth],dp);
      subSet(depth+1,N,nums,v,makedNum-nums[depth],dp);
      subSet(depth+1,N,nums,v,makedNum,dp);
  
  }

  • 부분탐색을 진행하는데 중복이 발생(v[depth][makedNum])하면 중복을 제거해주는 방식의 코드입니다.
  • 처음 부분에서 if(makedNum >= 0)를 사용한 이유는 v배열에 음수값을 넣으면 arrayindexoutofboundsexception가 발생하기 때문입니다. 얼핏 타당해 보이는 이유지만 이 부분이 문제를 틀린 이유입니다.
    makedNum는 음수가 가능합니다. 하지만 제 코드는 양수에 대해서만 방문처리를 해주고 있습니다. 그래서 음수가 되는 경우의 수에 대해 시간복잡도가 급격히 증가했던 겁니다.
  • 그럼 음수는 왜 발생할까요. 이 문제의 식은 다음과 같이 구성됩니다. 무게를 구하려는 물건 + 추1 + 추2 = 추3이면 해당 물건은 추1, 추2, 추3으로 무게를 측정할 수 있다는 의미가 됩니다. 그리고 우리는 해당 식을 무게를 구하려는 물건 = 추3 - 추2 - 추1로 변경하기 때문에 빼기가 발생합니다. 그리고 추1 -> 추2 -> 추3순으로 입력이 들어왔다면 -추1, -추1 - 추2, -추1 - 추2 + 추3으로 계산해 중간에 음수가 발생합니다.
    하지만 생각해보면 왼쪽에 -5의 추가 있는 것과 오른쪽에 5의 추가 있는 건 무게를 측정할 때 완전히 동일합니다. 그렇기 때문에 계산 결과가 음수라면 이를 양수로 바꿔도 아무런 지장이 없다는 얘기입니다.

정답

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] nums = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		boolean[] dp = new boolean[40001];
		boolean[][] v = new boolean[N+1][40001];
        // 부분집합
		subSet(0,N,nums,v,0,dp);
		
        // 정답 출력
		int T = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < T; i++) {
			int ball = Integer.parseInt(st.nextToken());
			if(dp[ball]) {
				sb.append("Y ");
			}else {
				sb.append("N ");
			}
		}
		System.out.println(sb.toString());

		
	}
	
	public static void subSet(int depth, int N, int[] nums, boolean[][] v, int makedNum, boolean[] dp) {

		// makedNum이라는 숫자는 주어진 추로 만들 수 있습니다.
		dp[makedNum] = true;
        // 이미 중복된 값이 존재하면 해당 경우의 수를 더이상 진행하지 않습니다. 
		if(v[depth][makedNum]) return;
		v[depth][makedNum] = true;	

		// 탈출 조건
		if(depth == N) {
			return;
		}
		
		subSet(depth+1,N,nums,v,makedNum+nums[depth],dp);
		subSet(depth+1,N,nums,v,(makedNum-nums[depth]<0)?nums[depth]-makedNum:makedNum-nums[depth],dp); // 음수 처리
		subSet(depth+1,N,nums,v,makedNum,dp);
		
	}
}