[백준] 20300번 서강근육맨 / Greedy Algorithm(탐욕법, 그리디 알고리즘)

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

20300번: 서강근육맨

---

문제

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

 

헬스장에 있는 N개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10개의 운동기구가 있을 경우 PT를 5번 받으면 모든 기구를 다 사용할 수 있다. 9개의 운동기구가 있는 경우에도 PT를 5번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

 

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다.

 

이때, M의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

 

---

내가 푼 코드

 

문제를 이해하는데 시간이 좀 필요했고..

그 다음에는 근손실 정도를 받는 배열을 int로 선언했다가 NumberFormatException 발생하였다.

원인 찾는데 힘 좀 쓴 거 같다(근손실 발생...ㅎㅎ;;)

 

탐욕법에 대해서 공부했을 때 정렬 기법을 함께 사용한다고 하여 Arrays.sort()로 정렬을 먼저 한 뒤에

근손실이 가장 적은 것 중에 가장 큰 값을 찾아야 하므로..

 

1) 운동기구가 짝수 일 때는 제일 작은 값 + 제일 큰 값을 계산하여 그 중에서 가장 큰 값을 max 변수에 집어넣었고

 

2) 운동기구가 홀수 일 때는 가장 큰 값(배열의 가장 마지막 index)을 max 변수에 집어 넣은 뒤 해당 index를 제외하고 제일 작은 값 + 제일 큰 값을 계산하여 그 중에서 가장 큰 값을 max 변수에 집어넣도록 풀었다.

 

n이 홀수이면서 1인 경우에는 계산할 필요도 없이 바로 max에 근손실 값을 집어넣었다.

 

조금이라도 시간을 줄이기 위해 for문을 돌릴 때는 n의 크기만큼이 아니라 반으로 잘라서 반만 돌도록 하였다. n이 홀수인 경우에는 배열의 마지막 값은 바로 max에 넣기때문에 계산할 필요가 없어서 n-1을 계산한 뒤 2로 나눠서 for문이 돌도록 하였다.

---

탐욕법에 대한 공부!

 

아래 영상을 참고하였다!

https://www.youtube.com/watch?v=PNPIk3hc6ic