[브론즈 2] 14471번: 포인트 카드

Original Source: https://www.acmicpc.net/problem/14471

14471번: 포인트 카드

---

문제

JOI 상점가에서는 포인트 카드 서비스를 실시하고 있다. 각 포인트 카드에는 도장을 찍을 수 있는 칸이 총 2N개 있어, 상품을 구매하면 뽑기를 해서 결과에 따라 '당첨' 또는 '꽝' 도장이 찍힌다. 한 칸에 두 번 이상 도장을 찍을 수는 없다. 2N개 중 N개 이상의 칸에 당첨 도장이 찍힌 포인트 카드는 경품과 교환할 수 있다. 또, 한 칸에 찍힌 도장을 1엔을 내고 다른 도장으로 바꿀 수 있다.

JOI 군은 2N개 칸을 다 채운 포인트 카드를 M장 가지고 있다. i번째 포인트 카드에는 Ai개의 당첨 도장과, Bi개의 꽝 도장이 찍혀 있다.

JOI 군은 M-1개 이상의 경품을 가지려고 한다. 이에 필요한 비용의 최솟값을 구하라.

입력

입력은 M+1줄로 이루어진다.

첫 줄에는 2개의 정수 N, M(1≤N≤1000,1≤M≤1000)이 공백을 사이에 두고 주어진다. 이는 포인트 카드에 2N개의 칸이 있고, JOI 군이 M장의 포인트 카드를 가지고 있음을 나타낸다.

다음 M개 줄 중 i번째(1≤i≤M) 줄에는 각각 2개의 정수 Ai, Bi (0≤Ai≤2N, 0≤Bi≤2N, Ai+Bi=2N)가 주어지며, 포인트 카드 i에 Ai개의 당첨 도장과 Bi개의 꽝 도장이 찍혀 있음을 나타낸다.

출력

JOI 군이 M-1개 이상의 경품을 얻기 위해 필요한 비용의 최솟값을 원 단위로 한 줄로 출력하라.

---

사고의 흐름

• M == 1일 경우 경품을 하나도 갖지 않아도 되므로 답이 무조건 0이겠네. 익스트림 케이스 조심해야겠다.
• 애초에 최소 비용만 구하면 되니까 어떤 카드에 얼마나 당첨 도장이 찍혀 있는지 조사할 필요가 없잖아? 그냥 모든 도장의 개수를 취합한 다음 과반수의 개수만 넘기면 되지 않나?
• 아니네. 도장이 N+1개 이상 찍혀 있는 카드를 제출하면 가지고 있던 당첨 도장이 N개를 초과해서 사라지니까.
• 그러면 당첨 도장의 개수가 N개 이상인 카드는 그냥 넘기고, N개 미만인 카드만 비용을 파악하면 되겠다.

 

• 이미 정렬이 된 리스트인데 굳이 맨 뒤의 원소를 제거할 필요가 있나? 값이 N 이상인 원소를 제거하는 과정에서 자동으로 사라질 것 같은데.

내가 작성한 소스코드

n, m = map(int, input().split())
stamps = []
for _ in range(m):
    stamps.append(input().split())

stamps_won = []
for i in range(m):
    stamps_won.append(int(stamps[i][0]))

stamps_won = sorted(stamps_won, reverse=True)
stamps_won = stamps_won[:-1]
stamps_won = [item for item in stamps_won if item < n]

if (len(stamps_won) > 0):
    print((n * len(stamps_won)) - sum(stamps_won))
else:
    print(0)

남이 작성한 소스코드

skcom 님:
https://www.acmicpc.net/source/6825430

피드백

• stamps_won 리스트를 따로 조작할 필요가 없이 for문에서 range를 m-1로 설정한 뒤 원소의 값이 n보다 작으면 그 차이만 합해 주면 된다.