딩코딩 : Computer Science 블로그

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

1. 문제설명

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과

시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와

그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

각 문제는 한번 씩만 풀 수 있고 최대 점수를 구해야 한다.

2. 접근 방법[알고리즘]

각 문제는 한 번만 풀 수 있으므로

다이나믹 테이블 dy에 for문을 뒤부터 돌면서

최댓값을 누적해주면 된다.

for문을 뒤부터 도는 이유는

이 문제는 각 단원 문제를 단 한 번씩 풀 수 있는데

앞에서부터 돌면 계속해서 중복된 값을 더해서 누적하기 때문이다.

중복된 값을 누적하는 걸 피하기 위해 뒤부터 돈다.

만약 각 단원 문제를 여러번 풀 수 있다면

for문을 앞에서 부터 돌아 계속 중복해서 누적해주면 된다.

3. 문제풀이코드 C++

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

int n, t, dy[10001];

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

	cin >> n >> t;
	for (int i = 0; i < n; i++) {
		int k, s;
		cin >> k >> s;
		for (int j = t; j >= k; j--) {
			dy[j] = max(dy[j], dy[j - k] + s);
		}
	}
	cout << dy[t];

}

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

1.문제설명

투자금액 N과 기업의 개수 M이 주어진다.

M개의 기업에 주어진 투자액수를 활용해 최대 이익을 얻어야 한다.

각각 기업은 최대 한번 투자할 수 있고, 투자하지 않아도 된다.

A에 4를 투자하고 B에 0을 투자하는 건 가능 하지만

A에 1을 투자하고 또 3을 투자하는 건 불가능 하다.

답으로 각 기업에 투자한 금액과, 얻을 수 있는 이익의 최댓값을 산출해야한다.

2. 접근방법[알고리즘]

다이나믹 프로그래밍이자 냅색 문제이다.

표를 만들어 각 투자액수에 대하여 얻을 수 있는 최대 이익을 갱신하면 된다.

단 이 문제가 까다로운 건 단순히 최대 이익을 구하는 게 아니라

각 기업에 투자한 금액을 저장해야 한다.

이를 위해 dy테이블을 2차원 배열로 만들어 최대 이익을 갱신할 때마다

각 기업에 투자한 금액 또한 누적했다.

[ 최대 이익, A에 투자한 금액, B에 투자한 금액]

점화식

dy 테이블에서 index가 0인 column에 이익 최댓값을 저장하고,

index 1 ~ m 까지 1부터 m번 기업까지에 투자한 액수를 저장한다.

최댓값은 다른 냅색, 배낭 문제처럼

단순히 dy[j][0] = dy[j-k][0] + arr[k][i]; 구할 수 있다.

if (dy[j][0] < dy[j - k][0] + arr[k][i]) {
    dy[j][0] = dy[j - k][0] + arr[k][i];

    for (int t = 1; t <= m; t++) {
        if (t == i) dy[j][i] = k;
        else dy[j][t] = dy[j - k][t];
    }
}

3. 문제풀이 코드 C++

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

int n, m, arr[301][21], dy[301][21];

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 1; i <= m; i++) {
		for (int j = n; j >= 0; j--) {
			for (int k = 0; k <= j; k++) {
				//k는 가격
				if (dy[j][0] < dy[j - k][0] + arr[k][i]) {
					dy[j][0] = dy[j - k][0] + arr[k][i];

					for (int t = 1; t <= m; t++) {
						if (t == i) dy[j][i] = k;
						else dy[j][t] = dy[j - k][t];
					}
				}

			}
		}
	}
	cout << dy[n][0] << '\n';

	for (int i = 1; i <= m; i++) {
		cout << dy[n][i] << ' ';
	}

}

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

다이나믹프로그래밍이자 냅색 문제이다.

문제 조건에 따라 체력은 100이 되면 안되서 99가 최대이다.

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

int n, cost[21], point[21], dy[101];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

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

	cout << dy[99];

}

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;
		}
	}


}

2차원

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

int n, m;
int dy[101][1020];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i=1; i<=n ;i++){
		int point, time;
		cin >> point >> time;
		
		for(int j = time; j<=m; j++){
			dy[i][j] = max(dy[i-1][j-time] + point, dy[i-1][j]);
		}
	}

	cout << dy[m];
	

}

1차원

for문을 뒤에서부터 돌면 해결된다

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

int n, m;
int dy[1020];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i=1; i<=n ;i++){
		int point, time;
		cin >> point >> time;
		
		for(int j = m; j>=time; j--){
			dy[j] = max(dy[j-time] + point, dy[j]);
		}
	}

	
	cout << dy[m];
	

}

첫 코드

DFS로 완전탐색을 했는데 시간이 초과되었다.

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

int n, m, res=INT_MIN;
vector<pair<int, int> > v;

void DFS(int value, int weight){
	if(weight > m) return;
	else{
		res = max(res, value);
		for(int i=0; i<v.size();i++){
			DFS(value + v[i].second, weight+v[i].first);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; i++){
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a,b));
	}
	
	DFS(0, 0);
	
	cout << res;
}

DP 이용

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

int n, m, bag[1001], res;
vector<pair<int, int > > v;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i=0; i<n; i++){
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a,b));	
	}

	for(int i=0; i<v.size(); i++){
		for(int j=0; j<=m; j++){
			if(j-v[i].first>=0){
				bag[j] = max(bag[j-v[i].first] + v[i].second, bag[j]);
			}
		}
	}

	for(int i=0; i<=m; i++){
		res = max(res, bag[i]);
	}
	cout << res;

}

더 간단한 코드

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

int n, m, bag[1001];

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

	cin >> n >> m;
	for(int i=0; i<n; i++){
		int w, v;
		cin >> w >> v;

		for(int j=w; j<=m; j++){
			bag[j] = max(bag[j-w] + v, bag[j]);
		}
	}
	cout << bag[m];

}

냅색 알고리즘은

무게를 0부터 n까지 돌 때

각 요소마다 가방에 넣었을 때 최댓값이 된다면 갱신해주면 된다.

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

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

	int n;
	cin >> n;
	vector<int> arr(n+1), dy(n+1);
	
	dy[0]=1;
	dy[1]=1;
	
	for(int i=1; i<=n; i++){
		cin>> arr[i];
	}
	for(int i=2; i<=n; i++){
		int maxx = 0;
		for(int j=i-1; j>=1; j--){
			if(arr[j]<arr[i]){
				maxx = max(dy[j], maxx);
			}
		}
		dy[i] = maxx+1;
	}
	
	int ans=0;
	
	for(int i=1; i<=n;i++){
		ans = max(ans, dy[i]);
	}
	
	cout << ans;
	
	
	
}