[BOJ 23891] 백준 23891번 - 타이어 끌기

		GBS Coding Contest 2021 풀이
A		[BOJ 23885] 비숍 투어
B		[BOJ 23886] 알프수
C		[BOJ 23887] 프린트 전달
D		[BOJ 23888] 등차수열과 쿼리
E		[BOJ 23889] 돌 굴러가유
F		[BOJ 23890] 달팽이팽이
G		[BOJ 23891] 타이어 끌기
H		[BOJ 23892] 바코드 찢기

1. 문제

$23891$. 타이어 끌기 (GBS Coding Contest 2021 Open G번)

백준 23891번 - 타이어 끌기 (https://www.acmicpc.net/problem/23891)

2. 풀이

$M$명을 $N$개의 타이어에 적절히 배정해서 최대 점수를 얻는 것이 목표이다.

하나의 타이어에서 더 많은 사람을 보낸 팀이 점수를 얻는다. 따라서, 1반을 승리로 이끌기 위해서 하나의 타이어에 대해서 취할 수 있는 ‘최적’의 행동은 총 세 가지가 있다. (점수를 잃으면 총점에서 빼는 방식으로 계산하여 점수가 양수면 이긴 것으로 간주한다.)

1. 2반보다 1명 더 배정하여 1반이 점수를 얻는다. (단 한 명만 더 앞서더라도 점수를 얻는 것이 가능하므로, 두 명 이상 앞서게 배정할 이유가 없다) $\rightarrow$ P[i]+1명을 배정하여 S[i]점을 얻음
2. 2반과 동일하게 배정하여 아무도 점수를 얻지 못한다. $\rightarrow$ P[i]명을 배정하여 점수 변화 없음
3. 아무도 배정하지 않고 2반이 점수를 얻는다. (어차피 점수를 잃을 것이므로 특정 인원을 배정할 이유가 없다) $\rightarrow$ $0$명을 배정하여 S[i]점을 잃음

이렇게 정리하면, 배정해야 하는 사람을 weight, 얻는 점수를 price로 간주하여 knapsack 문제와 동일하게 볼 수 있다. 위의 세 개의 선택지가 존재하는 knapsack으로 구현하면 된다.

3. 채점 결과

4. 회고

2반과 동일하게 배정하여 아무도 점수를 얻지 못하게 하는 방법을 고려하지 않고 구현하여 WA를 받았다.

5. 코드