해석이 이상할 수 있습니다.
이상한 부분은 말씀해 주시면 수정하겠습니다.
문제: https://codeforces.com/contest/915/problem/A
시간 제한: 1s
메모리 제한: 256MB
Luba 그녀의 정원에 물을 주는 것에대해 생각했다.
정원은 길이 k로 분할이 가능하다.
Luba는 n개의 버켓이 있고 i번의 물을 주는 것을 허용한다.
그녀는 한 시간에 정확히 ai 길이만큼 물을 나눠줄 수 있다.
Luba는 이미 물을 준 부분에는 줄 수 없고, 정원 밖에도 줄 수 없다.
Luba는 가능한 빨리 정원에 물을 주기위해 하나의 버켓을 선택해야 한다.(위에서 말한것처럼, 연속적으로 ai길이만큼 분할된 구역에 물을 준다, 만약 그녀가 i번째 버켓을 선택했다면).그녀가 정원에 물을 보내는 가장 작은 시간을 결정할 수 있도록 도와달라. 그것은 보장한다 Luba가 항상 하나의 버켓을 선택할 수 있으며 그것은 정원에 물을 줄 수 있다.
예를 보면 쉽게 이해할 수 있다.
[입력]
첫번 째 줄에는 정수 n 과 k 가 입력된다.(1 ≤ n, k ≤ 100)
- 각각 버켓과 가든의 길이
두번 째 줄에는 n개의 정수 ai가 입력된다.(1 ≤ ai ≤ 100)
-i번 버켓으로 시간 당 물을 줄 수 있는 분할된 공간의 길이
그것은 정원 안에 정수 시간동안 물을 주는 것이 가능한 버켓이 적어도 하나 이상 있다는 것을 보장한다
[출력]
하나의 정수가 출력된다-정원에 물을 주는 것이 가능한 최소한의 숫자(시간)
[풀이]
이 문제는 n개의 양동이 중 하나를 선택해서
그 양동이로 k만큼의 정원을 채울 때, 가장 적은 횟수로 채울 수 있게 해주는 양동이를 고르는 문제다.
단, 양동이로 물을 채우는 경우가 k를 넘어서는 안된다.
이 부분을 생각해보면 k는 i(양동이)로 나눠 떨어지는 숫자여야 한다는 것을 알 수 있다.
그렇다면 우리는 주어진 n개의 양동이들 중 k의 약수이면서 가장 큰 수 를 구하면 된다.(반드시 하나 이상의 약수가 존재한다.)
아래 코드를 보면 sort 를 해주었는데 이는 주어진 i(양동이)를 오름차순으로 배열하고 큰 수부터 k를 나눠주어 나머지가 0이 되는 수를 찾기 위함이다.
이 때 가장 먼저 나머지가 0이 되게하는 i가 최적의 양동이고
k를 i로 나눈 값(양동이로 물을 뜬 횟수)가 정답이 된다.
[코드]
https://github.com/Woobeen906/Codeforces/blob/main/915-A.cpp
문제를 풀면서...
알고리즘 실력도 부족하고 영어도 부족하다.
문제를 해석하는 시간도 어느정도 있고 해석한 문제를 다시 이해하는 것도 여간 힘든 일이 아닌 것 같다.
더 많은 문제를 풀어보고 꾸준히 노력하면 한글 문제만큼 빠르게 문제를 풀 수 있게 될 것이라 믿는다.
