| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 567 | 393 | 357 | 70.414% |
상필이는 크리스마스트리 장식에 사용하려고 $N$개의 전구를 구매했다. 이 전구에 전원을 연결하면 즉시 빛나지 않고 일정한 주기로 반짝인다. 주기가 $t$초인 전구는 전원을 연결하고 $t$초, $2\times t$초, $3\times t$초, $\cdots$가 지난 시각에 반짝인다.
상필이는 모든 전구에 전원을 연결하고 $T$초가 지난 시각에 모든 전구가 동시에 반짝이게 하고 싶다. 상필이는 전구에 전원을 연결하기 전에, $N$개의 전구 중 하나를 선택해 그 전구의 주기를 $1$초만큼 늘리거나 줄일 수 있다. 단, 주기를 $1$초보다 작아지게 할 수는 없다.
전구의 주기를 조절하는 과정을 통해 모든 전구에 전원을 연결하고 $T$초가 지난 시각에 모든 전구가 동시에 반짝이게 하려면 이 과정을 최소 몇 번 수행해야 하는지 구해보자.
첫째 줄에 전구의 개수 $N(1\le N\le 1\, 000)$과 정수 $T(1\le T\le 1\, 000)$가 공백으로 구분되어 주어진다.
둘째 줄에 정수 $a_1,a_2,\cdots ,a_N(1\le a_i\le 1\, 000)$이 공백으로 구분되어 주어진다. $a_i$는 $i$번째 전구의 주기가 몇 초인지를 의미한다.
모든 전구에 전원을 연결하고 $T$초가 지난 시각에 모든 전구가 동시에 반짝이게 하려면 이 과정을 최소 몇 번 수행해야 하는지 출력한다.
3 14 4 1 13
3
4 6 2 8 6 3
2
4 12 9 5 3 7
5
University > 충남대학교 > 2024 충남대학교 SW-IT Contest E번