백준 2629번: 양팔저울 - 냅색(배낭) 문제

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

2629번: 양팔저울

 

1. 문제 설명, 접근방법[알고리즘]

 

여러 개의 추가 주어졌을 때, 추들로 구슬 무게를 잴 수 있는 지 확인하는 문제입니다.

 

만약 추의 무게가 1과 4인 추 2개가 있다면

구슬 무게는 1, 4, (1+4), abs(1-4) 이렇게 잴 수 있습니다.

 

좀 더 일반화 해보면

1로 만들어 줄 수 있는 구슬의 무게는 (0+1), abs(0-1)

4를 추가해서 만들 수 있는 구슬의 무게는 (0+4), abs(0-4), ((0+1)+4), abs(abs(0-1)-4)

이렇게 될 것입니다.

 

x 무게의 추가 있다면

기존에 만들 수 있던 무게들(ex)에서

(ex + x) , abs(ex - x) 의 경우의 수가 추가 됩니다.

 

 

이를 구현하기 위해 bool 타입의 배열 dy를 만들고

추를 하나씩 더해가면서 특정 구슬의 무게를 만들 수 있는지 없는지 체크합니다.

그리고 dy[0] = true로 초기화 해줍니다.

 

만들 수 있는 구슬의 무게	0	1	2	3	4	5
1g 추	true	true(0+1, abs(0-1)	false	false	false	false
4g 추	true	true	false	true(abs(4-1))	true(0+4)	true(4+1)

 

 

점화식

	dy[0] = true;
	for (int i = 0; i < n; i++) {
		for (int j = chu_max; j >= 0; j--)
			if (dy[j]) dy[j + chu[i]] = 1;
		for (int j = 0; j <= chu_max; j++)
			if (dy[j]) dy[abs(j - chu[i])] = 1;
	}

일차원 배열로 다이나믹 테이블을 만들었을 때 중요한 점이

for 문을 도는 순서입니다.

 

새로운 추를 도입하기 전에 지정된 true값을 한 번씩만 사용해야 하는데

위의 코드처럼 for문 방향을 해주지 않으면

dy[j]에 대해 체크하고 또 for문을 돌면서 체크하고

앞으로 나아가면서 계속 true로 만들어 버립니다.

 

 

더할 때는 뒤에서부터 돌고, 뺄 때는 앞에서부터 돌면

이전에 사용한 추로 만든 true값을 한 번씩만 사용합니다.

 

2. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, chu[31], m, chu_max;
bool dy[40001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> chu[i];
		chu_max += chu[i];
	}
	
	dy[0] = true;
	for (int i = 0; i < n; i++) {
		for (int j = chu_max; j >= 0; j--)
			if (dy[j]) dy[j + chu[i]] = 1;
		for (int j = 0; j <= chu_max; j++)
			if (dy[j]) dy[abs(j - chu[i])] = 1;
	}


	//for (int j = 0; j <= chu_max; j++) {
	//	cout << dy[j] << " ";
	//}
	//cout << '\n';


	cin >> m;
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		if (dy[tmp]) cout << "Y ";
		else cout << "N ";
	}
}

처음에 추 무게가 최대가 500g * n=30 = 15000이어서

다이나믹 테이블 dy 범위를 15000까지 잡아주었는데

문제에서 구슬 Input이 40000까지 들어오기 때문에

dy[40001] 로 해주어야 OutOfBounds를 피할 수 있다.