[파이썬/python] 백준 - 32200 항해

문제

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

---

문제 설명

1.   $N$개의 샌드위치가 존재한다.
2. 최소 $X$cm이상,  최대 $Y$cm이하의 길이로 샌드위치를 잘라서 먹을 것이다.
   
   1. 샌드위치를 잘랐을 때 $X$cm 미만이 남았다면 버린다.
3. 샌드위치로 해결할 수 있는 끼니 개수의 최댓값과 버려지는 샌드위치 조각의 합의 최솟값을 구해라.

 

---

풀이

1. 현재 샌드위치의 길이가 $X$cm 보다 작다면 나머지에 더한다.
2. 샌드위치를 먹을 수 있는 최솟값인 X로 나누었을 때 몫과 나머지를 구한다.
3. 2에서 구한 나머지를 최솟값으로 나눈 샌드위치에 더해가며 최소의 나머지를 구한다.

 

예시

문제에 나와있는 1번 예제로 예시를 들어보자.

1. $[11,10,17,5,23,28]$ 총 6개의 샌드위치가 존재한다.

2. 최소 10cm ~12cm로 샌드위치를 먹을 것이다.

 

11 = 10 + 1

1. 최소인 10으로 자른 후 1이 남았으므로 1개의 샌드위치에 나머지 1을 붙인다.

10 = 10 + 0

1. 최소인 10으로 자른 후 나머지가 없으므로 나머지 0을 더한다.

17 = 10 + 7

1. 최소인 10으로 자르면 1조각이 나오고 나머지 7이 남는다.
2. 각 조각(10cm)에 나머지를 붙여 총 나머지를 줄인다. -> 12 + 5
3. 나머지 5를 더한다.

5 = 0 + 5

1. 최소인 10으로 자를 수 없기 때문에 나머지 5를 더한다.

23 = 10 + 10 + 3

1. 최소인 10으로 자르면 2조각이 나오고 나머지 3이 남는다.
2. 각 조각(10cm)에 나머지를 붙여 총 나머지를 줄인다. -> 12 + 11 + 0
3. 나머지 0을 더한다.

28 = 10 + 10 + 8

1. 최소인 10으로 자르면 2조각이 나오고 나머지 8이 남는다.
2. 각 조각(10cm)에 나머지를 붙여 총 나머지를 줄인다. -> 12 + 12 + 4
3. 나머지 4를 더한다.

 

 

---

코드

import sys
n,x,y = map(int,input().split())
sws = list(map(int,input().split()))

cnt = 0
least = 0
for sw in sws:
    if sw < x:
        least += sw
    else:
        crnt_cnt = sw // x
        crnt_least = sw % x
        cnt += crnt_cnt
        if crnt_least > crnt_cnt * (y-x):
            least += (crnt_least - crnt_cnt * (y-x))
print(cnt)
print(least)

---

시간복잡도

• 샌드위치의 최대 수 $N = 4 * 10^4$
• 내부 연산은 상수로 취급하여 약 $O(10^4)$ 정도의 시간복잡도를 가진다.