중급반 4주차 풀이 - 냅색, 구간 DP

1. [1535] 안녕 (Silver II)

\( DP_{i, j} := \) \( i \)번째 사람까지 인사 여부를 결정했을 때, 체력을 최대 \( j \)만큼 써서 얻을 수 있는 최대 행복

이라고 정의합시다.

그럼 \( DP_{i, j} \)는 2가지 경우에 의해 결정됩니다.

• \( i \)번 사람에게 인사를 한다: \( DP_{i-1, j-L_{i}} + J__{i} \)만큼의 기쁨을 느낍니다.
• \( i \)번 사람에게 인사를 하지 않는다: \( DP_{i-1, j} \)만큼의 기쁨을 느낍니다.

문제의 답은 \( DP_{N, 99} \)가 됩니다.
* 100의 체력을 쓰면 죽기 때문에 최대 체력은 99여야 합니다.

시간복잡도는 \( O(100N) \)입니다.

pi2 arr[22]; int dp[22][120];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr; }
	for (int i = 1; i <= n; i++){ cin >> arr[i].sc; }
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < 100; j++){
			dp[i][j] = dp[i-1][j];
			int cst = arr[i].fr, val = arr[i].sc;
			if (j >= cst){
				dp[i][j] = max(dp[i][j], dp[i-1][j-cst] + val);
			}
		}
	}
	cout << dp[n][99];
}

0-1 Knapsack도 사실 1차원 배열로 구현할 수 있습니다.

Unbounded Knapsack과의 차이점은, \( j \)를 최댓값부터 돌린다는 점입니다.

이렇게 돌리면, 어떤 하나의 물건이 2번 연속으로 계산될 수 없게 됩니다.

pi2 arr[22]; int dp[120];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr; }
	for (int i = 1; i <= n; i++){ cin >> arr[i].sc; }
	for (int i = 1; i <= n; i++){
		for (int j = 99; j >= 0; j--){
			int cst = arr[i].fr, val = arr[i].sc;
			if (j >= cst){
				dp[j] = max(dp[j], dp[j-cst] + val);
			}
		}
	}
	cout << dp[99];
}

사실 이 문제는 냅색 없이도 풀 수 있습니다.

사람의 수가 최대 20명이므로, 인사를 하는 경우의 수는 \( 2^{20} = 1 \, 048 \, 576 \)가지밖에 되지 않습니다.

이 모든 경우를 하나하나 돌리면서 기쁨의 최댓값을 계산해주면 됩니다.

 

시간복잡도는 \( O(N2^{N}) \)입니다.

int n; pi2 arr[22];

int ans = 0;
void btk(int idx, int lft, int val){
	if (lft <= 0){ return; }
	if (idx > n){ ans = max(ans, val); return; }
	btk(idx+1, lft, val); btk(idx+1, lft-arr[idx].fr, val+arr[idx].sc);
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr; }
	for (int i = 1; i <= n; i++){ cin >> arr[i].sc; }
	btk(1, 100, 0);
	cout << ans;
}

2. [1106] 호텔 (Silver I)

\( DP_{i} := \) \( i \)명을 늘리기 위해 사용해야 하는 최소 비용 을 정의해봅시다.

그럼 \( a \)원을 들여서 \( b \)명을 불러온다고 할 때 \( DP_{i} = \min (DP{i}, DP_{i-b} + a) \)가 됩니다.

* \( DP_{i} \)의 초깃값은 \( DP_{0} = 0 \)를 제외하면 \( \infty \)여야 합니다.

 

위 식을 각각의 \( (a, b) \) 쌍에 대해 돌려주면 됩니다.

const int M = 2000;
const ll INF = 1e15; ll dp[2020];

void Main(){
	memset(dp, -1, sizeof(dp)); dp[0] = 0;
	int n, m; cin >> m >> n;
	for (int i = 1; i <= n; i++){
		int a, b; cin >> a >> b;
		for (int j = b; j <= M; j++){
			if (dp[j-b] == -1){ continue; }
			if (dp[j] == -1){ dp[j] = INF; }
			dp[j] = min(dp[j], dp[j-b]+a);
		}
		//cout << "DP "; for (int j = 0; j <= 20; j++){ cout << dp[j] << ' '; } cout << endl;
	}
	ll ans = INF;
	for (int i = m; i <= M; i++){
		if (dp[i] == -1){ continue; }
		ans = min(ans, dp[i]);
	}
	cout << ans;
}

3. [11066] 파일 합치기 (Gold III)

\( DP_{st, ed} := \) \( [st, ed] \) 구간의 파일들을 합치기 위한 최소 비용 이라고 정의합시다.

 

그럼 \( [st, ed] \) 구간의 파일을 어떻게 합칠까요?

\( st \le k \lt ed \)인 어떤 위치 \( k \)에 대해, \( [st, k] \)를 합치고 \( (k, ed] \)를 합쳤다고 합시다.

그 다음에는 위 두 구간을 합쳐야 하며, 이 때의 추가 비용은 \( \sum_{i=st}^{ed} A_{i} \)가 됩니다.

추가 비용이 구간의 합 형태이므로, 누적합을 사용하면 빠르게 계산할 수 있습니다.

그러니, 점화식으로 보면 \( DP_{st, ed} = \min_{st \le k \lt ed} (DP_{st, k} + DP_{k+1, ed}) + PRF_{ed} - PRF_{st-1} \)가 됩니다.

 

초항은 \( DP_{i, i} = 0 \)이고, 답은 \( DP_{1, N} \)입니다.

시간복잡도는 \( O(N^3) \)입니다.

const ll INF = 1e15;
ll arr[520], prf[520]; ll dp[520][520];
inline ll sum(int st, int ed){ return prf[ed] - prf[st-1]; }

void Main(){
	int t; cin >> t;
	while (t--){
		int n; cin >> n;
		for (int i = 1; i <= n; i++){ cin >> arr[i]; }
		for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
		for (int l = 2; l <= n; l++){
			for (int st = 1; ; st++){
				int ed = st+l-1; if (ed > n){ break; }
				dp[st][ed] = INF; ll val = sum(st, ed);
				for (int k = st; k < ed; k++){
					dp[st][ed] = min(dp[st][ed], dp[st][k]+dp[k+1][ed] + val);
				}
			}
		}
		cout << dp[1][n] << endl;
	}
}

4. [2629] 양팔저울 (Gold III)

\( DP_{i, j} := \) \( i \)번째 추까지 사용할 수 있을 때 무게가 \( j \)인 구슬을 측정할 수 있는가?

를 정의하면, 아래 3가지 경우 중 하나를 통해서 DP의 점화식을 정의할 수 있게 됩니다.

• \( i \)번 추를 사용하지 않음: \( DP_{i-1, j} \)
• \( i \)번 추를 구슬의 반대쪽에 놓음: \( DP_{i-1, j - W_{i}} \)
• \( i \)번 추를 구슬과 같은 쪽에 놓음: \( DP_{i-1, j + W_{i}} \)

최종 점화식은 \( DP_{i, j} = DP_{i-1, j} \text{ or } DP_{i-1, j-W_{i}} \text{ or } DP_{i-1, j+W_{i}} \)가 됩니다.
* \( j \)가 범위를 나갔다가 다시 안으로 들어와서 가능해지는 경우, \( j \)가 음수로 가는 경우 등 생각보다 고려할 경우가 많습니다. 저의 경우는 가능한 무게를 \( 40000 \times 30 \)으로 잡아줬습니다.
** 아니면 그냥 제가 구현을 잘못한 거일 수도 있습니다.

각 구슬별 답은 \( DP_{N, w} \)이며, 시작하기 전에 위 과정을 다 계산해준 뒤 출력만 해주면 됩니다.

const int N = 1200000;
bool dp[32][2400020];

void Main(){
	int n; cin >> n;
	dp[0][N] = 1;
	for (int i = 1; i <= n; i++){
		int w; cin >> w;
		for (int jj = -N; jj <= N; jj++){
			int j = jj+N;
			dp[i][j] |= dp[i-1][j];
			if (j-w >= 0){ dp[i][j] |= dp[i-1][j-w]; }
			if (j+w <= N+N){ dp[i][j] |= dp[i-1][j+w]; }
			//if (dp[i][j]){ cout << "DP " << i << ' ' << jj << endl; }
		}
	}
	int q; cin >> q;
	while (q--){
		int x; cin >> x;
		cout << (dp[n][x+N] ? 'Y' : 'N') << ' ';
	}
}

5. [12865] 평범한 배낭 (Gold V)

이름부터 냅색의 향기를 풍기는 문제입니다.

그러니까 진짜 냅색으로 풀어주면 됩니다.

 

냅색을 까먹은 사람들을 위해: \( i \)번 물건의 (무게, 가치) = \( (w, v) \)라고 할 때

\( DP_{i, j} := \) \( i \)번 물건까지 고려할 때 무게 \( j \)의 가방으로 담을 수 있는 최대 가치

\( DP_{i, j} = \max (DP_{i-1, j}, DP_{i-1, j-w} + v) \)

답: \( DP_{N, K} \)

이 문제는 0-1 Knapsack 문제로, 1차원 배열로도 풀 수 있습니다.

pl2 arr[120]; ll dp[100020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	for (int i = 1; i <= n; i++){
		for (int j = m; j >= 0; j--){
			ll cst = arr[i].fr, val = arr[i].sc;
			if (j >= cst){
				dp[j] = max(dp[j], dp[j-cst] + val);
			}
		}
	}
	cout << dp[m];
}

6. [10942] 팰린드롬? (Gold III)

\( DP_{st, ed} := \) \( [st, ed] \)가 팰린드롬인가? 를 봅시다.

\( [st, ed] \) 구간의 수열이 팰린드롬이려면, \( A_{st} = A_{ed} \)여야 하고, \( (st, ed) \) 구간의 수열도 팰린드롬이어야 합니다.

즉, \( DP_{st, ed} = DP_{st+1, ed-1} \text{ and } (A_{st} = A_{ed}) \)가 됩니다.

 

초항은 \( DP_{i, i} = \text{True}; DP_{i, i+1} = (A_{i} = A_{i+1}) \)이고, 답은 \( DP_{st, ed} \)입니다.

시간복잡도는 \( O(N^2 + M) \)입니다.

int arr[2020];
bool dp[2020][2020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){ dp[i][i] = 1; }
	for (int i = 1; i < n; i++){ dp[i][i+1] = (arr[i] == arr[i+1]); }
	for (int l = 3; l <= n; l++){
		for (int st = 1; ; st++){
			int ed = st+l-1; if (ed > n){ break; }
			dp[st][ed] = dp[st+1][ed-1] && arr[st] == arr[ed];
		}
	}
	int q; cin >> q;
	while (q--){
		int st, ed; cin >> st >> ed;
		cout << dp[st][ed] << endl;
	}
}

7. [11049] 행렬 곱셈 순서 (Gold III)

"3. [11066] 파일 합치기"와 뭔가 비슷하게 풀 수 있을 것 같으니, 비슷하게 DP를 정의해봅시다.

\( DP_{st, ed} := \) \( [st, ed] \) 구간의 행렬들을 합치기 위한 최소 연산 횟수

 

점화식도 비슷하게 구해봅시다.

\( st \le k \lt ed \)인 어떤 위치 \( k \)에 대해, \( [st, k] \)를 합치고 \( (k, ed] \)를 합쳤다고 합시다.

이 때 만들어지는 행렬의 크기는 각각 \( (\text{height of }A_{st} \times \text{width of }A_{k}) \)과 \( (\text{height of }A_{k+1} \times \text{width of }A_{ed}) \)가 됩니다.

앞으로는 \( N = \text{height of }A_{st}, M = \text{width of }A_{k} = \text{height of }A_{k+1}, K = \text{width of }A_{ed} \)라고 하겠습니다.

 

행렬이 2개밖에 남지 않았으니, 이제 그 두 행렬을 합쳐야 하며, 이 때의 추가 연산 횟수는 \( NMK \)가 됩니다.

그러니, 점화식으로 보면 \( DP_{st, ed} = \min_{st \le k \lt ed} (DP_{st, k} + DP_{k+1, ed} + NMK) \)가 됩니다.

 

초항은 \( DP_{i, i} = 0 \)이고, 답은 \( DP_{1, N} \)입니다.

시간복잡도는 \( O(N^3) \)입니다.

const ll INF = 1e15;
pl2 arr[520];
ll dp[520][520];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	for (int l = 2; l <= n; l++){
		for (int st = 1; ; st++){
			int ed = st + l-1;
			if (ed > n){ break; }
			dp[st][ed] = INF;
			for (int mid = st; mid < ed; mid++){
				dp[st][ed] = min(dp[st][ed], dp[st][mid] + dp[mid+1][ed] + arr[st].fr*arr[mid].sc*arr[ed].sc);
			}
		}
	}
	cout << dp[1][n];
}

8. [1750] 서로소의 개수 (Gold II)

\( DP_{i, j} := \) \( i \)번째 수까지 고려했을 때 최대공약수를 \( j \)로 만드는 경우의 수 라고 정의합시다.

그러면 점화식은 아래 두 경우로 볼 수 있습니다.

• \( i \)번째 수를 사용하지 않는다: \( DP_{i, j} \) += \( DP_{i-1, j} \)
• \( i \)번째 수를 사용한다: \( DP_{i, \gcd(j, S_{i})} \) += \( DP_{i-1, j} \)
• + \( i \)번째 수만 사용한다: \( DP_{i, S_{i}} \) += \( 1 \)

2번 경우의 점화식의 좌변이 \( DP_{i, \gcd(j, S_{i})} \)임에 주의하세요.

시간복잡도는 \( O(NM) \)입니다.

int gcd(int a, int b){ if (b == 0){ return a; } return gcd(b, a%b); }

const int M = 100000, mod = 10'000'003;
int dp[52][100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		int x; cin >> x; dp[i][x] += 1; dp[i][x] %= mod;
		for (int j = 1; j <= M; j++){
			dp[i][j] += dp[i-1][j]; dp[i][x] %= mod;
			dp[i][gcd(j,x)] += dp[i-1][j]; dp[i][gcd(j,x)] %= mod;
		}
		/* for (int j = 1; j <= M; j++){
			if (dp[i][j]){ cout << "DP " << i << ' ' << j << " = " << dp[i][j] << endl << flush; }
		} */
	}
	cout << dp[n][1];
}

아래의 이상한 풀이밖에 생각이 나지 않은 덕분에 중급반 풀이를 도저히 못 내겠어서 JJaewon9님의 코드를 읽어봤습니다. (다만 위의 코드는 풀이 이해 후 제가 작성했습니다.) JJaewon9님 감사합니다.

중급반의 선을 신나게 넘는 풀이이지만, 제가 이렇게 풀었기에 올립니다.

\( f(x) := \) 최대공약수가 \( x \)의 배수인 경우의 수 를 정의합시다.

그럼, 포함-배제의 정리에 의해 답은 \( f(1) - f(2) - f(3) - f(5) + f(6) - f(7) + f(10) \cdots \)가 됩니다.

정확히는, \( \sum_{i=1}^{10^5} \mu(i) \cdot f(i) \)가 답이 됩니다. 여기서 \( \mu(x) \)는 뫼비우스 반전 공식입니다.

 

이제, \( f(x) \)를 구해봅시다.

이건 간단한데, 수열에서 \( x \)의 배수의 개수를 \( C \)라고 하면, \( 2^C - 1 \)가지 경우가 가능합니다.

 

이제 필요한 건 다 나왔으니, 구현해주면 됩니다.

const int N = 100000, M = 50;
const ll mod = 10'000'003;
int num[100020], cnt[100020]; ll two[60];
int pf[100020], mob[100020];

void Main(){
	two[0] = 1; for (int i = 1; i <= M; i++){ two[i] = two[i-1]*2 % mod; }
	for (int i = 2; i <= N; i++){
		if (pf[i]){ continue; }
		for (int j = i; j <= N; j+=i){ pf[j] = i; }
	}
	memset(mob, -1, sizeof(mob)); mob[1] = 1;
	for (int i = 2; i <= N; i++){
		int p = pf[i];
		if (i/p % p == 0){ mob[i] = 0; }
		else{ mob[i] = mob[i/p]*mob[p]; }
	}
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ int x; cin >> x; num[x] += 1; }
	for (int i = 1; i <= N; i++){
		for (int j = i; j <= N; j+=i){ cnt[i] += num[j]; }
	}
	//for (int i = 1; i <= 20; i++){ cout << "CNT " << i << " = " << cnt[i] << ' ' << two[ cnt[i] ]-1 << ' ' << mob[i] << ' ' << endl; }
	ll ans = 0;
	for (int i = 1; i <= N; i++){ ans += mob[i] * (two[ cnt[i] ]-1); ans += mod; ans %= mod; }
	cout << ans;
}

9. [23257] 비트코인은 신이고 나는 무적이다 (Gold III)

이번에는 bitwise XOR입니다.

\( DP_{i, j} := \) \( i \)개의 수를 골라서 \( j \)를 만들 수 있는가? 를 정의하고, 식을 세워봅시다.

 

+ 실제로는 값의 절댓값을 써야 하지만, 어차피 입력받으면서 abs() 씌워주면 되므로 지금부터는 \( A_{i} \ge 0 \)이라고 보겠습니다.

 

\( k \)번째 수를 사용한다면, \( i-1 \)개의 수로 \( j \oplus A_{k} \)를 만든 뒤 \( i \)번째 수로 \( A_{k} \)를 사용해주면 됩니다. 즉, \( DP_{i, j} = DP_{i, j} \text{ or } DP_{i-1, j \oplus A_{k}} \)가 됩니다.

 

DP를 다 돌린 뒤, \( DP_{M, j} = \text{True} \)인 최대의 \( j \)를 찾아주면 됩니다.

int arr[120]; bool dp[120][1030];
const int MAX = 1024;

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; arr[i] = abs(arr[i]); }
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			for (int k = 0; k < MAX; k++){
				dp[j][k] |= dp[j-1][arr[i]^k];
			}
		}
	}
	for (int i = MAX-1; i >= 0; i--){
		if (dp[m][i]){ cout << i; return; }
	}
}

10. [12920] 평범한 배낭 2 (Platinum IV)

물건을 \( K \)개로 다 나눠서 돌리는 건 힘들 것 같으니, \( \log^2 K \)개의 물건으로 나눠봅시다.

\( \log \)가 붙은 걸 보면 2의 제곱수로 하면 될 것 같은데...

 

진짜 2의 제곱수를 써줄 수 있습니다.

우선 1개를 빼낸 뒤, 2개를 빼낼 수 있으면 2개를 빼내고, 4개를 빼낼 수 있으면 4개를 빼내고, ...

이렇게 가다가 \( 2^i \)개를 빼낼 수 없는 상태가 되면 다시 1개부터 빼내기 시작하면 됩니다.

\( 2^i \)개의 물건을 하나로 묶으면 무게와 가치가 \( 2^i \)배가 됩니다.

2의 제곱수만으로 \( [1, K] \) 구간의 수를 다 쓸 수 있다는 건 자명하니 생략하겠습니다.

 

이제 물건의 개수가 \( N \log^2 K \)개가 되었으니 이대로 0-1 냅색을 돌려주면 됩니다.

ll dp[10020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		int w, v, k; cin >> w >> v >> k;
		int two = 1, sum = 0;
		while (sum < k){
			int wei = w*two, val = v*two;
			for (int j = m; j >= wei; j--){
				dp[j] = max(dp[j], dp[j-wei] + val);
			}
			sum += two; two *= 2; if (two > k-sum){ two = 1; }
		}
	}
	cout << dp[m];
}

이 문제도 풀이를 못 내겠어서 뚫은 덕분에, 정해를 모르는 상태였습니다. 그래서 nick832님의 코드를 읽어본 뒤 작성하는 풀이 및 코드입니다. nick832님 감사합니다.

중급반의 선을 신나게 넘는 풀이를 또 했습니다. 이번에는 문제 풀이도 아니고 문제 뚫기를 했습니다.

 

일단 무게가 같은 물건들을 모아봅시다.

무게가 같으면 가치가 더 큰 걸 쓰는 게 최적이므로, 가치 순으로 정렬해봅시다.

이렇게 하면 무게가 \( W \)인 물건은 최대 \( \lfloor 10000 / W \rfloor \)개밖에 넣을 수 없으므로, 여기서 커팅이 발생하게 됩니다.

 

또한, 무게가 1인 물건들을 냅색을 돌리기 전에 따로 처리해주면, 여기서 또 다른 커팅이 발생하게 됩니다.

마지막으로, 커팅 국룰 Ofast까지 넣어주면 됩니다.

시간복잡도는... 아마 \( O(M + \sum_{w=2}^{M} ((M-w) \cdot \lfloor M/w \rfloor) \)로, \( M = 10000 \)일 때 약 754,443,986회의 연산을 하게 됩니다. 하지만 알아서 잘 돌아줄 것이라는 믿음을 가지면 AC를 받을 수 있습니다.

#pragma GCC optimize("Ofast")

pi3 arr[10020];
int dp[10020], lim[10020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++){
		dp[i] = -1; lim[i] = m/i;
	}
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr.fr >> arr[i].fr.sc >> arr[i].sc; }
	sort(arr+1, arr+n+1, [](pi3 a, pi3 b){
		if (a.fr.fr != b.fr.fr){ return a.fr.fr < b.fr.fr; }
		return a.fr.sc > b.fr.sc;
	});
	int cnt = 0;
	int i; for (i = 1; i <= n; i++){
		int w = arr[i].fr.fr, x = arr[i].fr.sc, c = arr[i].sc;
		if (arr[i].fr.fr != 1){ break; }
		if (cnt >= m){ continue; }
		int st = cnt+1, ed = min(cnt+c, m);
		for (int j = cnt+1; j <= ed; j++){ dp[j] = dp[j-1] + x; }
		cnt += c;
	}
	for (; i <= n; i++){
		int w = arr[i].fr.fr, x = arr[i].fr.sc, c = arr[i].sc;
		if (w != arr[i-1].fr.fr){ cnt = 0; }
		while (c--){ cnt += 1;
			if (cnt > lim[w]){ break; }
			for (int j = m; j >= w; j--){
				if (dp[j-w] == -1){ continue; }
				dp[j] = max(dp[j], dp[j-w]+x);
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= m; i++){ ans = max(ans, dp[i]); }
	cout << ans;
}

11. [10982] 행운쿠키 제작소 (Platinum V)

\( a, b \) 2개를 관리해야 하지만, 만약 \( a \)를 고정해버린다면 고려해야 하는 건 \( b \)만 남게 됩니다.

이 점을 사용하여 DP를 정의해봅시다.

\( DP_{i, a} := \) \( i \)번째 반죽까지 구울 때, 1번 오븐이 \( a \)시간동안 일할 때 2번 오븐이 일해야 하는 최소 시간

 

이제 점화식을 두 경우로 나눠서 세워봅시다.

• 1번 오븐에 넣는 경우: \( DP_{i-1, j-a} \)
• 2번 오븐에 넣는 경우: \( DP_{i-1, j} + b \)

문제의 답은 \( DP_{N, a} = b \)일 때 \( \max(a, b) \)의 최솟값이 됩니다.

+ DP를 그대로 저장하면 MLE가 뜰 수 있으니 중급반 2주차에 있었던 "[2096] 내려가기"에서 썼던 Sliding Windows를 사용해서 메모리를 절약해야 합니다.

const int N = 100000;
const ll INF = 1e18; ll dp[2][100020];

void Main(){
	int t; cin >> t;
	while (t--){
		int n; cin >> n;
		for (int i = 0; i <= N; i++){ dp[0][i] = dp[1][i] = INF; }
		dp[0][0] = 0;
		for (int m = 1; m <= n; m++){
			int i1 = ~m&1, i2 = m&1;
			//cout << "REINDEXING " << m << ' ' << i1 << ' ' << i2 << endl;
			int a, b; cin >> a >> b;
			for (int i = 0; i <= N; i++){
				if (i-a >= 0){ dp[i2][i] = min(dp[i2][i], dp[i1][i-a]); }
				dp[i2][i] = min(dp[i2][i], dp[i1][i]+b);
				//if (dp[i2][i] != INF){ cout << "DP " << m << ' ' << i-DIF << " = " << dp[i2][i] << endl; }
			}
			for (int i = 0; i <= N; i++){ dp[i1][i] = INF; }
		}
		int idx = n&1;
		ll ans = INF;
		for (int i = 0; i <= N; i++){
			if (dp[idx][i] == INF){ continue; }
			//cout << "DP " << dif << " = " << dp[idx][i] << ' ' << dp[idx][i]+dif << endl;
			ans = min( ans, max((ll)i, dp[idx][i]) );
		}
		cout << ans << endl;
		//cout << flush;
	}
}

Special Thanks to

• JJaewon9 (8번 문제 도움)
• nick832 (10번 문제 도움)