[백준] 2629 - 양팔저울

[문제링크]

2629번: 양팔저울

 

0. 최대 무게 500g인 추가 최대 30개 들어오므로, 최대 탐색 가능 범위는 -15000 ~ 15000

 

1. 추를 올리지 않는 경우, 물건의 반대편에 올리는 경우(+), 물건쪽에 올리는 경우(-) 3가지 경우를

모든 추에 대해 재귀로 진행하며, 이 과정에서 거치는 모든 무게를 true로 표시한다.

  - 이때, 추를 추가한 무게가 앞 재귀에서 나왔던 무게일 경우, 중복 연산이 발생하므로 진입하지 않는다 (가지치기) 

 

2. 물건의 무게를 입력받고, 15000초과의 무게일 경우 즉시 N을, 그 이하일 경우 true/false 값에 따라 Y/N을 출력해준다.

 

추가적으로 생각해본 개선점

1. dfs처럼 재귀를 돌며 깊은 단계에 진입 때문에, 깊은 단계에서 possible 배열이 수정되어도

  얕은 단계에 영향을 주지 못하도록 possible배열이 2중으로 구현되어야 했음.

  - bfs처럼 큐에 넣어가며 단계별로 작업했다면 possible 배열 하나로 가능하지 않았을까?

 

2. -7500 값은 적어도 500g추 15개가 있어야 도달 가능한 값이므로,

  나머지 추 15개를 전부 +로 설정해도 0이상의 값을 가질 수 없다.

  - -7500 ~ 15000으로 possible 배열을 사용하면 크기를 25%정도 절약할 수 있었음.

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

public class Main {
	static int num;
	static int[] weight;
	static boolean[][] possible;
    
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		
		num=Integer.parseInt(br.readLine());
		weight = new int[num];
		
		//추 무게 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < num; i++) {
			weight[i]=Integer.parseInt(st.nextToken());
		}
		
		//해당무게의 표현 가능 여부 표시를 위한 boolean배열
		//추는 500g이하, 30개이하이므로, 최대 +15000, 최소 -15000까지 탐색할 수 있다
		//15000 지점을 가상의 0으로 가정, 30001개의 배열로 선언한다.
		possible = new boolean[30001][num];
		
		//추에 대한 선택지는 3가지 - 올리지 않는다|구슬쪽에 올린다|반대편에 올린다
		//3가지 선택지를 탐색하며 모든 계산 가능한 경우를 true로 마크한다
		search(0, 15000);//초깃값은 가상의 0인 15000

		//구슬의 개수 입력받기
		int ball_num = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < ball_num; i++) {
			int ball_weight = Integer.parseInt(st.nextToken());
			//최대 무게인 15000을 넘으면 바로 N
			if(ball_weight>15000) {
				sb.append("N ");
			}
			//해당 무게가 가능하다면 Y, 아니면 N을 기록한다.
			else sb.append(possible[ball_weight+15000][num-1]?"Y ":"N ");
		}
		System.out.println(sb);
	}
    
	static void search(int cnt, int cur) {
		//모든 추에 대해 탐색 종료
		if(cnt==num) {
			return;
		}
		else {
			//해당 무게에 도달한 적 없다면 진입한다
			if(!possible[ cur+weight[cnt] ][cnt]) {
				possible[ cur+weight[cnt] ][cnt]=true;
				search(cnt+1, cur+weight[cnt]);
			}
			//해당 무게에 도달한 적 없다면 진입한다
			if(!possible[ cur-weight[cnt] ][cnt]) {
				possible[ cur-weight[cnt] ][cnt]=true;
				search(cnt+1, cur-weight[cnt]);
			}
			//올리지 않는다
			possible[cur][cnt]=true;
			search(cnt+1, cur);
		}
	}
}

결과 화면