[백준] 포인트 카드 : 14471번 - Python

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

14471번: 포인트 카드

 

 

 

문제의 접근 방법

 

- 내림차순 정렬

- 이미 당첨 도장의 개수가 M보다 큰 A값을 제외한 나머지 경우의 수만 생각하기

   나머지 경우의 수가 M-1이 될 때까지 계산.

- 경품의 개수가 충족이 되지 않아서 도장을 바꿔야할 때 내는 1엔이 비용에 들어감.

- 최소 비용을 구해야 하기 때문에 M-1에서 M보다 작은 A값들의 개수를 빼준 횟수만큼만 반복문을 돌려서 바꿔야 할 도장의 개수(1엔씩)를 확인하기

 

 

내가 막혔던 부분

 

- 처음에 N,M의 값을 제대로 활용하지 못해서 어려움을 겪음.

 

 

 

문제 풀이 방법

 

(1) N,M 값을 입력받기

 

(2) 카드 교환 없이 경품을 얻을 수 있는 카드 개수를 카운트할 변수 cnt와 그렇지 못한 카드들(A,B)을 담을 빈 리스트 ard 선언하기

 

(3) A,B 값을 입력받기

- 만약 A값이 N보다 작다면 카드 교환이 필요하다는 것이므로 위에서 선언해 둔 리스트 card에 추가하기

- 그렇지 않다면, 이미 당첨도장이 N개 이상이라는 뜻이므로 위에서 선언해 둔 변수 cnt에 1씩 누적해서 더하기

 

(4) 최소 비용을 구하기 위해 가장 카드 교환 횟수가 적을 수 있는 수부터 나열하기 (내림차순 정렬 = 당첨 도장 A의 값이 가장 커야 교환해야 할(1엔을 지불하고) 카드가 적기 때문에 내림차순으로 정렬해야 함.)

 

(5) 최종 결과를 출력할 변수 result 선언하기

 

(6) M-1개의 경품을 받을 수 있는지 체크하고 그렇지 않다면 비용이 얼마나 드는지 출력하기

- 만약 M-1이 cnt랑 같다면 카드를 교환할 필요없이 이미 경품을 받을 수 있는 개수를 충족한다는 뜻이므로 0(비용이 들지 않음)을 출력해주기

- 그렇지 않다면, M-1-cnt 만큼의 반복문을 돌려서 리스트 card의 제일 i번째 요소의 가장 첫 번째 값을 N에서 빼준 후 result에 누적해서 더해주기

- 결과값 result 출력하기

 

 

 

소스코드

N,M = map(int, input().split()) # 포인트 카드에 2N개의 칸이 있고 M장의 포인트 카드를 가지고 있음

card = []
cnt = 0     # 경품을 얻을 수 있는 카드의 개수를 카운트

for _ in range(M):
    A, B = (map(int, input().split()))    # A개의 당첨도장와 B개의 꽝 도장이 찍혀있음
    if A < N: 
        card.append([A, B])
    else:
        cnt += 1

card.sort(reverse=True)

result = 0
if (M-1) == cnt:
    print(0)
else:
    for i in range(M-1-cnt):
        result += (N - card[i][0])
    print(result)