[Python] BOJ(백준) 2217번 - 로프 (+ sys.stdin.readline의 중요성)

링크

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

난이도(solved.ac 참고)

실버3

풀이

문제 풀이 방법은, 그냥 내림차순으로 나열한 다음에 a_list[인덱스] * (인덱스+1)의 최댓값을 구하면 끝난다. a_list[인덱스]는, 예제의 경우 내림차순하면 15 10 이 되는데, 각 로프에 모두 고르게 중량이 걸리게 되므로 15를 선택한다면 15만큼만 들 수 있고, 10을 선택한다면 (10 * 2) = 20만큼 들 수 있다. 이 생각을 토대로, a_list[인덱스]의 값은 작아지고 인덱스는 커지는 상황에서 결국 들 수 있는 값인 a_list[인덱스] * (인덱스 + 1)의 최댓값을 구한 것이다.

(여기서 인덱스+1을 해 준 이유는, 인덱스는 0부터 시작하기 때문이다.)

 

사실 어려운 문제는 전혀 아니었다. 쉬운 문제인데, 여기서 크게 깨달은 점이 있다.

두 코드의 시간 차이는 어마어마하다. 아래 5452ms가 나온 코드는 input을 썼고, 156ms가 나온 코드는 상기한 코드처럼 sys.stdin.readline을 썼다. 알고리즘을 막 시작했을 때 친구들이 다 input 말고 sys.stdin.readline을 쓰길래 이게 뭐냐고 물어봤던 기억이 났다. 그 때는 그냥 좀 더 빠르다고 하길래 그런가보다 하기만 했는데, 실제로 이렇게 엄청난 차이를 보이는 것을 보니 앞으로 꼭 sys.stdin.readline을 써야겠다고 생각했다.