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

ALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 4. 22:49

1. [1535] 안녕 (Silver II)

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

이라고 정의합시다.

그럼 $D P_{i, j}$ 는 2가지 경우에 의해 결정됩니다.

$i$ 번 사람에게 인사를 한다: $Missing open brace for subscript$ 만큼의 기쁨을 느낍니다.
$i$ 번 사람에게 인사를 하지 않는다: $D P_{i - 1, j}$ 만큼의 기쁨을 느낍니다.

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

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

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 (N 2^{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)

$D P_{i} :=$ $i$ 명을 늘리기 위해 사용해야 하는 최소 비용 을 정의해봅시다.

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

* $D P_{i}$ 의 초깃값은 $D P_{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)

$D P_{s t, e d} :=$ $[s t, e d]$ 구간의 파일들을 합치기 위한 최소 비용 이라고 정의합시다.

그럼 $[s t, e d]$ 구간의 파일을 어떻게 합칠까요?

$s t \leq k < e d$ 인 어떤 위치 $k$ 에 대해, $[s t, k]$ 를 합치고 $(k, e d]$ 를 합쳤다고 합시다.

그 다음에는 위 두 구간을 합쳐야 하며, 이 때의 추가 비용은 $\sum_{i = s t}^{e d} A_{i}$ 가 됩니다.

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

그러니, 점화식으로 보면 $D P_{s t, e d} = min_{s t \leq k < e d} (D P_{s t, k} + D P_{k + 1, e d}) + P R F_{e d} - P R F_{s t - 1}$ 가 됩니다.

초항은 $D P_{i, i} = 0$ 이고, 답은 $D P_{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)

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

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

$i$ 번 추를 사용하지 않음: $D P_{i - 1, j}$
$i$ 번 추를 구슬의 반대쪽에 놓음: $D P_{i - 1, j - W_{i}}$
$i$ 번 추를 구슬과 같은 쪽에 놓음: $D P_{i - 1, j + W_{i}}$

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

각 구슬별 답은 $D P_{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)$ 라고 할 때

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

$D P_{i, j} = max (D P_{i - 1, j}, D P_{i - 1, j - w} + v)$

답: $D P_{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)

$D P_{s t, e d} :=$ $[s t, e d]$ 가 팰린드롬인가? 를 봅시다.

$[s t, e d]$ 구간의 수열이 팰린드롬이려면, $A_{s t} = A_{e d}$ 여야 하고, $(s t, e d)$ 구간의 수열도 팰린드롬이어야 합니다.

즉, $D P_{s t, e d} = D P_{s t + 1, e d - 1} and (A_{s t} = A_{e d})$ 가 됩니다.

초항은 $D P_{i, i} = True; D P_{i, i + 1} = (A_{i} = A_{i + 1})$ 이고, 답은 $D P_{s t, e d}$ 입니다.

시간복잡도는 $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를 정의해봅시다.

$D P_{s t, e d} :=$ $[s t, e d]$ 구간의 행렬들을 합치기 위한 최소 연산 횟수

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

$s t \leq k < e d$ 인 어떤 위치 $k$ 에 대해, $[s t, k]$ 를 합치고 $(k, e d]$ 를 합쳤다고 합시다.

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

앞으로는 $N = height of A_{s t}, M = width of A_{k} = height of A_{k + 1}, K = width of A_{e d}$ 라고 하겠습니다.

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

그러니, 점화식으로 보면 $D P_{s t, e d} = min_{s t \leq k < e d} (D P_{s t, k} + D P_{k + 1, e d} + N M K)$ 가 됩니다.

초항은 $D P_{i, i} = 0$ 이고, 답은 $D P_{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)

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

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

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

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

시간복잡도는 $O (N M)$ 입니다.

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) \dots$ 가 됩니다.

정확히는, $\sum_{i = 1}^{10^{5}} μ (i) \cdot f (i)$ 가 답이 됩니다. 여기서 $μ (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입니다.

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

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

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

DP를 다 돌린 뒤, $D P_{M, j} = 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$ 인 물건은 최대 $⌊ 10000 / W ⌋$ 개밖에 넣을 수 없으므로, 여기서 커팅이 발생하게 됩니다.

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

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

시간복잡도는... 아마 $O (M + \sum_{w = 2}^{M} ((M - w) \cdot ⌊ M / w ⌋)$ 로, $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를 정의해봅시다.

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

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

1번 오븐에 넣는 경우: $D P_{i - 1, j - a}$
2번 오븐에 넣는 경우: $D P_{i - 1, j} + b$

문제의 답은 $D P_{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번 문제 도움)

'ALOHA - 2022 > ALOHA - 중급반 (2022 1학기)' 카테고리의 다른 글

중급반 6주차 풀이 - 최단경로 (BFS, 다익스트라) (0)	2022.05.18
중급반 5주차 풀이 - DFS, BFS, 백트래킹 (0)	2022.05.12
중급반 3주차 풀이 - 이진 탐색, 파라메트릭 서치, 두 포인터 (1)	2022.05.04
중급반 2주차 풀이 - 그리디, DP, 분할 정복 (0)	2022.05.02
중급반 1주차 풀이 - Brute Force (0)	2022.04.30

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

인기포스트

ABOUT ME

hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

1. [1535] 안녕 (Silver II)

2. [1106] 호텔 (Silver I)

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

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

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

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

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

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

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

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

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

'ALOHA - 2022 > ALOHA - 중급반 (2022 1학기)' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

인기포스트

ABOUT ME

1. [1535] 안녕 (Silver II)

2. [1106] 호텔 (Silver I)

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

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

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

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

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

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

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

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

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

'ALOHA - 2022 > ALOHA - 중급반 (2022 1학기)' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역