딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/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로 초기화 해줍니다.

점화식

	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를 피할 수 있다.

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

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

다이나믹프로그래밍 문제이자 배낭 문제이다.

"현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여

M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다."

M바이트의 메모리를 확보하는 게 아니라

M바이트 이상의 메모리를 추가로 확보해야 한다.

나는 처음에 이전에 배낭문제를 풀었던 걸 기억해서

무지성으로 메모리를 기준점을 잡고 비용의 최솟값을 갱신해나가려 했는데

그러면 메모리의 범위가 1 ≤ M ≤ 10,000,000 이어서 배열의 최대 사이즈를 넘어 사용할 수가 없다.

그런데 알고보니 메모리를 기준점으로 하는 게 아니라

비용을 기준점으로 하면 비용의 최댓값이 100이고 n의 최댓값이 100이어서

배열을 dy[10001]로 잡아주면 충분하다.

dy[i] 는 cost가 i 일 때 최대 확보한 메모리이다.

점화식

dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);

문제처럼 입력이 다음과 같을 때

5 60
30 10 20 35 40
3 0 3 5 4

dy 테이블은

각 문제를 적용했을 때 확보된 메모리가 60이상인 최소의 비용은

6이다.

문제풀이코드 C++

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

int n, m, mem[101], cost[101], dy[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> mem[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> cost[i];
	}


	for (int i = 0; i < n; i++) {
		for (int j = 10000; j >= cost[i]; j--) {
			dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);
		}
	}

	for (int i = 0; i <= 10000; i++) {
		if (dy[i] >= m) {
			cout << i;
			break;
		}
	}


}