[백준 / Python] 14627번 파닭파닭

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

14627번: 파닭파닭

[문제 해석]

이 문제는 이분 탐색 문제로, 최소값과 최대값을 고려하면서 적절한 값을 찾아가는 문제이다.

이 문제에서 주의할 점은 라면에 넣을 파의 양이라는 점이다.

 

---

[소스코드]

S, C = map(int, input().split())

pa = []
for _ in range(S) :
    pa.append(int(input()))

start, end = 1, max(pa)

while start <= end :
    mid = (start + end) // 2

    tmp = sum(i//mid for i in pa)

    if tmp >= C :
        start = mid + 1

    else :
        end = mid - 1

noodle = sum(pa) - (C * end)
print(noodle)

---

[문제 해결]

최솟값을 start, 최대값을 end로 설정하여 반복문을 돌린다.

이때, 메모리 사용량으로 인해 start를 1로, end을 max(pa)로 설정한다.

​

그리고 start와 end의 중간값인 mid를 설정해 이 mid값을 기준으로 이분탐색을 하도록 한다.

tmp에 pa 리스트에 있는 원소값을 mid로 나눈 나머지 값을 모두 더하여 대입한다.

​

그리고 그 tmp값이 목표치 이상일 경우 mid에 1을 더하여 start에, 목표치 미만일 경우 mid - 1 하여 end에 대입한다.

​

본 문제에서 주목할 점은 파닭에 최대로 사용한 후의 나머지 파의 양을 구하는 것이다.

end는 파닭에 사용한 파의 최대 양이므로, 전체 파의 양에서 (end * 파닭의 개수)만큼을 뺀 후 그 값을 출력한다.

​

그 값이 라면에 넣은 파의 양이다.

 

---

[오류 해결]

​

본 문제에서 언어를 Python3으로 설정했을 때 계속해서 시간 초과 오류가 있었다.

메모리를 계속 최대한으로 사용하기 위해 계속 코드를 수정해보았으나 오류가 해결되지 않았다.

결국, 언어를 PyPy3으로 수정함으로써 오류를 해결할 수 있었다.

​

---

원문 : https://www.acmicpc.net/problem/14627