[BaekJoon] "그리디" - 백준 20300번 문제 : 서강근육맨

[문제 설명]

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

20300번: 서강근육맨

 

PT를 한 번 받을 때 운동 기구를 최대 두 개까지만 선택 가능

향빈이는 N.개의 운동 기구를 한 번씩 사용해 보고 싶음 

PT를 받을 때마다 이전에 사용하지 않았던 운동 기구를 선택하기로 함

PT를 받을 때 운동 기구를 되도록이 면 두 개를 사용하기로 함

총 10개의 운동 기구가 있다면, PT를 5번 받으면 모든 기구 다 사용 가능

근데, 근손실도 고려해야함. PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 함

이때 M의 최솟값을 구해야 함

참고로 운동 기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동 기구의 근손실 정도의 합

 

[해결 로직]

- 먼저 근손실 정도가 저장된 리스트를 정렬함

- 가장 작은 값과 가장 큰 값을 더해야 최소의 근손실 값이 됨

- 만약, 기구가 짝수일때는 처음과 끝값을 더하면서 max 값을 찾음 

- 여기서 max인 경우는 min으로 하면 다른 날 PT를 할때의 근손실 값이 그 값을 넘을 수 있음

- 만약 기구 개수가 홀수라면? 맨 뒤에 가장 큰 수를 max 값으로 미리 저장

- 맨 끝값을 제외한 나머지 기구들의 근손실이 가장 작은 값과 큰 값을 더하면서

- 미리 저장된 max 값보다 큰지 확인, 크다면 update

 

[Solution 코드]

n = int(input())

ary = list(map(int, input().split()))

ary = sorted(ary)
rslt = -9999999999
if len(ary) % 2 == 0 : ## 짝수일때
    for i in range(n//2):
        tmp = ary[i] + ary[n-i-1]
        rslt = max(tmp, rslt)
else:## 홀수 일때도 마찬가지
    # 근데 홀수일때는 맨 뒤에 (가장 큰 수) 수를 먼저 rslt에 저장
    rslt = ary[-1]
    for i in range(n//2):
        tmp = ary[i] + ary[n-i-2]
        rslt = max(tmp, rslt)
print(rslt)

 

뭐가 그리디 인지를 잘 찾고 생각해야 한당