급하게임개발

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

솔직히 이 문제는 못 풀었다 풀이를 보고나서 이해를 할 수 있었다 이 문제의 코드는 그리 길지 않지만 하나의  로직을 아는사람이 풀 수 있었다.  핵심로직은 내가 어떠한 무게추를 들고 있다고 가정하자 일단 1이라는 무게추가 있다고 가정 하자 1이라는 무게추가 있을 때 다음 무게추가 지금 내가 가지고 있는 무게추의 무게보다 크게 되면 사이 무게인 2를 만들 수없다.

다른 예시로 현재 내가 1,1,2 이렇게 총 3개의 무게추를 가지고 있는데 다음 무게추로 6이 들어오게 되면 나는 4를 만들 수  없다

즉 현재 내가 가지고 있는 총 무게추의 무게보다 작은 무게들을 다 만들 수 있을 때 다음에 사용할 무게추는 내가 가지고 있던 총 무게보다 작아야 한다.

해당  로직이 이문제를 풀 수 있게 하는 핵심 로직이었다

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int arr[1000];

int main() {

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    sort(arr, arr + N);

    int res = 1;
    for (int i = 0; i < N; i++) {
        if (arr[i] > res) {
            break;
        }
        res += arr[i];
    }

    cout << res;
}

이 문제는 dp문제이다

#include <iostream>
#include <algorithm>
using namespace std;
//dp[i][j]= 처음부터 i번째 까지의 물건을 살펴보고, 배낭의 용량이 j였을 떄 배낭에 들어간 물건의 가치합의 최댓값
//예를 들어
int dp[101][100001];
int W[101];
int V[101];
int main() {
	//N은 물건의 갯수를 의마한다.
	//K는 버틸수 있는 물건의 무게를 의미한다.
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}


	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			if (j - W[i] >= 0) {
				//현재 무게의 최댓갑은 이전아이템까지 넣은 단계에서의 최댓값과
				//지금 아이템의 무게를 넣은 물건의 값을 비교하여 더 큰값을 넣는다.
				//i번째 물건을 넣을 지 말지가 중요하다.
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]]+V[i]);
			}
			else {
				//현재 아이템을 넣었을때 무게가 오바된다면 넣지 않고 이전걸 그대로 가져온다
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[N][K];
}

코드를 살펴보면 일다 우리는 가지고 있는 첫번째 아이템 부터 차근차근 가방에 넣을 것이다. 차근차근 넣을 때 제한 무게를 초과한다면 그 아이템은 넣지 않는다가 이문제의 핵심이다. 즉 i번째 아이템을 넣은 것과 안 넣은 것의 최댓값을 계속 갱신해주면서 진행하는게 해당 문제의 해결 방법이다. i=1일때 우리는 가방에 이 아이템을 넣을지 말지 결정 한다. dp[0][0]은 어차피 0이다 하지만 무게해당하는 j값이 0이기에 일단 넣지 않는다. 이에 dp[1][6]=13이다 즉 1번아이템을 넣었을 때의 무게는 6이고 13이다라는 의미이다 이제 2번아이템을 넣는다고 가정해보자 2번아이템도 마찬가지로 진행이된다. dp[4][4]의 가치는 일단 8이다 하지만 이제 dp[6]으로 간다면 2번까지 넣어서 6이하의 무게를 만든 가방보다 1번만 넣어서 6이하의 무게를 가진 가방의 가치가 더높으므로 dp[2][6]=13이다. 

자이제 3번아이템까지 넣는다고 가정하자  일단 dp[3][3]=6이다 dp[2][4]=8이고 이에 따라 dp[3][4]=8이다

dp[3][7]의 기준으로 보자 지금 까지는 dp[1][6]의 값이 계속 들어 와서 13이었을 것이다. 하지만 3번 아이템을 넣는다고 가정해보았을 때 dp[2][4]+dp[3][3] 즉 dp[2][4]+V[i]의 값이 기존의 dp[2][7]즉 dp[1][6]의 값이 계속 넣어진 상황 보다 큼으로

갱신된다