[백준] 29160번 나의 FIFA 팀 가치는? (파이썬 / Python)

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

29160번: 나의 FIFA 팀 가치는?

 

24/02/08 현재 난이도: 실버2

쓰이는 알고리즘: 자료구조(힙) , 정렬

내가 생각하는 난이도: 실버 1~2

남의 도움을 받았는가?: X

 

 

들어가기전에 서론

이문제는 작년  SUPAC L번 문제였다.

나는 이번 SUAPC에 참여한다.

팀원과 함께 SUAPC 버츄얼을 돌리던중 만난 문제인데

다른문제들의 비해 난이도가 낮아 들어오게되었다.

2번의 틀렸습니다 후에 문제를 맞췄는데

처음보자마자 풀이는 떠올랐으나, 두 번 다 문제의 조건을 제대로 읽지 않아 발생한 문제였다.

틀렸던 이유는 마지막에 설명하겠다.

 

 

본론으로 들어가서 이제 문제풀이에 대한 이야기를 해보자

 

처음 문제를 보자마자 1번부터 11번까지 후보선수들의 가치를 저장해놓고 최대한 높은것을

가지고와서 그것을 더하고 1년에 한번 내가 선택한 후보의 가치를 1을 떨어트리면 되겠구나 싶었다

후보선수들의 가치중 최대한 높은것을 가지고 오고 1을 낮춰서 내놓는 방법은

1년이 지날 때마다 sort를 한다면 N의 시간 복잡도를 가지므로 시간적으로 분리 하다고 생각하여

힙이라는 자료구조를 생각해냈다. 힙이라는 자료구조는 pop을 했을때 최솟값을 빼는 자료구조이다.

하지만 나는 최댓값을 꺼내고싶으므로 가치의 음의값을 저장했다.

그래서 힙을 이용하여 선수의 가치를 업데이트해주면 logN의 시간에 선수의 가치가 업데이트 된다

 

이제 나의 정답을 받은 코드를 보며 이야기해보자

 

 

입력이 많을수도 있으므로(N이 최대 100만) 빠른 입출력을 적어줬고

graph라는 이름으로 1번부터 11번 선수의 후보들을 저장할 리스트를 만들어줬다

1번 선수후보들은 graph의 인덱스 1안에 있는 리스트에 힙이라는 자료구조로 저장될 것이다.

11번 선수후보들은 graph의 인덱스 11안에 있는 리스트에 힙이라는 자료구조로 저장될 것이다.

이렇게 모든 선수들이 리스트안에 힙이라는 자료구조로 저장이 되는것이다

 

그래프를 선언한후 후보선수의 번호와 가치를 받아 graph[hubo]에 -value값을 push해줬다.

그런후 K년후에 구단가치를 원하는데 선수는 1년에 두번 가장가치가 높은 선수로 교체한다

그래서 U를 1부터 2K까지 돌게 하고싶으므로 range(1,2K+1) 까지를 돌려줬다

그리고 내가 구해야하는 그 순간의 구단가치를 dap이라고 하고 처음에 0으로 선언했다

x가 그래프의 1번선수 후보 부터 11번 선수 후보들까지 돌면서 만약 x가 비어있지 않으면

가장 큰 가치를 갖는 선수를 뽑아내주기 위해 heappop을 해줬다.

그리고 가치를 -값으로 저장해놨으므로 답에 -v(가장 높은 가치를 가진 선수)를 더해줬고

8월에는 무조건 가치가 1이 낮아지므로 만약 u가 홀수 이면 선수의 가치를 1을 낮춰서 다시 후보 리스트(힙)에 넣어줬다

따라서 x에 v+1을 push해줬다 (v를 -값으로 저장했으므로 +1을 해야 절댓값이 낮아짐)

하지만 선수의 가치가 0아래로는 내려가지 않으므로 만약 v가 0이된다면 1을 더하지 않고 넣어줬다.

그리고 만약에 u가 짝수이면 가치변화는 없으므로 그대로 v를 다시 넣어줬다.

 

이렇게하면 계속해서 dap이 초기화 돼, 마지막에 팀에 가치를 dap이 기록하게 된다

따라서 dap을 출력하면 결과가 나오게된다.

 

여기까지가 이 문제의 풀이이다.

 

힙이라는 자료구조를 생각해내는게 그나마 어려운 부분이었고 문제를 잘 읽어

1년에 두 번 팀을 결성하는것과 선수의 가치가0보다 낮을 수는 없다를 잘 읽었어야 했다

 

위에서 말한 나의 첫번째 틀렸습니다의 이유는 문제를 잘 읽지않아 1년에 두번 팀을 결성한다는 것을

제대로 읽지 않았다. 그리고 두번째 틀렸습니다의 실수는 선수의 가치가 0보다 낮을 수 없다를 잘 읽지않아

선수의 가치가 음이 될때까지 해줘버렸다.

 

그 이후 문제를 천천히 다시 읽어 풀어냈다.

 

문제를 잘 읽자....