백준 23891 (C++) 타이어 끌기

최초 업로드: 2025-08-04 06:44:10

최근 수정 시간: 2025-08-04 06:45:09

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 타이어 끌기

[문제 링크](https://www.acmicpc.net/problem/23891)

## 문제 설명

타이어 끌기는 경기북과학고등학교의 운동회를 대표하는 인기 종목이다.

타이어 끌기의 규칙은 다음과 같다.

<ol>
	<li>$N$개의 타이어가 있으며, $i$번째 타이어는 $S_i$의 점수를 가진다.</li>
	<li>양 팀에서는 각 타이어마다 해당 타이어를 끌어올 사람의 수를 배정한다.</li>
	<li>각 타이어에 대해 더 많은 사람을 보낸 팀이 $S_i$만큼의 점수를 얻으며, 배정된 사람이 같은 경우 양 팀 모두 해당 타이어에 대한 점수를 얻지 못한다.</li>
	<li>더 많은 점수를 얻은 팀이 승리한다.</li>
</ol>

1학년 1반의 브레인인 당신은 스파이를 통해 상대 팀인 1학년 2반이 타이어 별로 배정한 인원을 알게 되었다.

타이어의 개수 $N$, 1학년 1반의 학생 수 $M$, 각 타이어가 가지는 점수와 1학년 2반이 배정한 인원이 주어질 때, 1학년 1반을 승리로 이끌 수 있을지 판단해보자.

## 입력

첫째 줄에 타이어의 개수 $N$, 1학년 1반의 학생 수 $M$이 주어진다.

이후 $N$개의 줄에 걸쳐 $i$번째 타이어의 점수 $S_i$, 해당 타이어에 1학년 2반이 배정한 학생 수 $P_i$가 주어진다.

주어지는 수들은 모두 양의 정수임이 보장된다.

## 출력

1학년 1반이 승리하는 것이 가능하다면 <code>W</code>, 비기는 것이 최대라면 <code>D</code>, 어떤 경우에도 패배하게 된다면 <code>L</code>을 출력한다.

## 풀이
#### 쉬운 냅색 활용 문제이다. 이기는 경우는 p+1명을 소비해서 s점을 얻고, 비기는 경우는 p명을 소비해서 0점을 얻고, 지는 경우는 0명을 소비해서 -s점을 얻는 형태로 구현하였다.

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

const int MAX = 100'001;
const long long MLINF = -0x3f3f3f3f3f3f3f3f;

long long dp[MAX];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    fill(dp, dp+MAX, MLINF);
    dp[0]=0;

while(n--) {
 int s, p; cin >> s >> p;
 long long nextDp[MAX];
 fill(nextDp, nextDp+MAX, MLINF);
 for(int i=0;i<=m;i++) {
 nextDp[i] = max(nextDp[i], dp[i]-s);
 if(i+p<=m) nextDp[i+p] = max(nextDp[i+p], dp[i]);
 if(i+p+1<=m) nextDp[i+p+1] = max(nextDp[i+p+1], dp[i]+s);
 }
 memcpy(dp, nextDp, sizeof dp);
 }
 long long maxScore = *(max_element(dp, dp+MAX));
 cout << (maxScore>0 ? "W" : maxScore==0 ? "D" : "L");
}
```