-
2012. [Python]등수 매기기Python_알고리즘/Silver III 2023. 5. 24. 22:13
1. 문제
https://www.acmicpc.net/problem/2012
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 256MB
- 그리디 알고리즘
- 정
3. 파이썬 코드
import sys # 인풋이 많기 떄문에 sys로 받는다 input = sys.stdin.readline N=int(input()) # 숫자 리스트 생성 num_list = [] for _ in range(N): num_list.append(int(input())) # 들어온 숫자를 오름차순 정렬 num_list.sort() # check라는 변수로 순위를 1~N까지 하기때문에 1로 설정 check = 1 # 기대값과 순위 차이를 계산 total = 0 # num_list 안의 변수를 모두 순회 for i in num_list: # abs 사용하는 것보다 조건식으로 해결 큰값에서 작은값 빼도록 if check > i: total += check - i else: total += i - check # 매 계산 후 등수 +1 check += 1 print(total)
4. 문제를 풀고난 후 생각
- 들어온 점수를 오름차순 정렬하여 1등부터 N 등까지 증가해가며 본인이 예상한 점수와 차이점을 구하는 방식을 선택했다.
- 등수의 기대값이 최소값이 되기 위해서는 1점부터 N 점까지 올라가며 예상 등수를 빼주는 식으로 계산하면 최소값의 합이 된다.
ex) 1 5 3 3 4 라는 점수가 주어진 경우 1 3 3 4 5 로 리스트를 정렬한다.
=> 1등부터 5등까지 1씩 증가하며 각각 기대값의 차이를 계산해준다.
=> 1-1 + 3-2 + 3-3 + 4-4 + 5-5 이런 식으로 계산하면 최소값이 나온다.
5. 문제를 푸는데 도움이 되는 지식
- 그리디 알고리즘
- 구현
'Python_알고리즘 > Silver III' 카테고리의 다른 글
2407. [Python]조합 (0) 2023.05.26 1614. [Python]영식이의 손가락 (0) 2023.05.26 1735. [Python]분수 합 (0) 2023.05.23 1935. [Python]후위 표기식2 (0) 2023.05.23 10974. [Python]모든 순열 (0) 2023.05.21