2021. 12. 4. 00:03γETC/Algorithm
μ΄λΆνμ κ΄λ ¨ λ¬Έμ !
λ¬Έμ μ€λͺ
nλͺ μ΄ μ κ΅μ¬μ¬λ₯Ό μν΄ μ€μ μμ κΈ°λ€λ¦¬κ³ μμ΅λλ€. κ° μ κ΅μ¬μ¬λμ μλ μ¬μ¬κ΄λ§λ€ μ¬μ¬νλλ° κ±Έλ¦¬λ μκ°μ λ€λ¦ λλ€.
μ²μμ λͺ¨λ μ¬μ¬λλ λΉμ΄μμ΅λλ€. ν μ¬μ¬λμμλ λμμ ν λͺ λ§ μ¬μ¬λ₯Ό ν μ μμ΅λλ€. κ°μ₯ μμ μ μλ μ¬λμ λΉμ΄ μλ μ¬μ¬λλ‘ κ°μ μ¬μ¬λ₯Ό λ°μ μ μμ΅λλ€. νμ§λ§ λ 빨리 λλλ μ¬μ¬λκ° μμΌλ©΄ κΈ°λ€λ Έλ€κ° κ·Έκ³³μΌλ‘ κ°μ μ¬μ¬λ₯Ό λ°μ μλ μμ΅λλ€.
λͺ¨λ μ¬λμ΄ μ¬μ¬λ₯Ό λ°λλ° κ±Έλ¦¬λ μκ°μ μ΅μλ‘ νκ³ μΆμ΅λλ€.
μ κ΅μ¬μ¬λ₯Ό κΈ°λ€λ¦¬λ μ¬λ μ n, κ° μ¬μ¬κ΄μ΄ ν λͺ μ μ¬μ¬νλλ° κ±Έλ¦¬λ μκ°μ΄ λ΄κΈ΄ λ°°μ΄ timesκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, λͺ¨λ μ¬λμ΄ μ¬μ¬λ₯Ό λ°λλ° κ±Έλ¦¬λ μκ°μ μ΅μκ°μ return νλλ‘ solution ν¨μλ₯Ό μμ±ν΄μ£ΌμΈμ.
μ νμ¬ν
- μ κ΅μ¬μ¬λ₯Ό κΈ°λ€λ¦¬λ μ¬λμ 1λͺ μ΄μ 1,000,000,000λͺ μ΄νμ λλ€.
- κ° μ¬μ¬κ΄μ΄ ν λͺ μ μ¬μ¬νλλ° κ±Έλ¦¬λ μκ°μ 1λΆ μ΄μ 1,000,000,000λΆ μ΄νμ λλ€.
- μ¬μ¬κ΄μ 1λͺ μ΄μ 100,000λͺ μ΄νμ λλ€.
μ μΆλ ₯ μ
n | times | return |
6 | [7, 10] | 28 |
κ°μ₯ 첫 λ μ¬λμ λ°λ‘ μ¬μ¬λ₯Ό λ°μΌλ¬ κ°λλ€.
7λΆμ΄ λμμ λ, 첫 λ²μ§Έ μ¬μ¬λκ° λΉκ³ 3λ²μ§Έ μ¬λμ΄ μ¬μ¬λ₯Ό λ°μ΅λλ€.
10λΆμ΄ λμμ λ, λ λ²μ§Έ μ¬μ¬λκ° λΉκ³ 4λ²μ§Έ μ¬λμ΄ μ¬μ¬λ₯Ό λ°μ΅λλ€.
14λΆμ΄ λμμ λ, 첫 λ²μ§Έ μ¬μ¬λκ° λΉκ³ 5λ²μ§Έ μ¬λμ΄ μ¬μ¬λ₯Ό λ°μ΅λλ€.
20λΆμ΄ λμμ λ, λ λ²μ§Έ μ¬μ¬λκ° λΉμ§λ§ 6λ²μ§Έ μ¬λμ΄ κ·Έκ³³μμ μ¬μ¬λ₯Ό λ°μ§ μκ³ 1λΆμ λ κΈ°λ€λ¦° νμ 첫 λ²μ§Έ μ¬μ¬λμμ μ¬μ¬λ₯Ό λ°μΌλ©΄ 28λΆμ λͺ¨λ μ¬λμ μ¬μ¬κ° λλ©λλ€.
λ¬Έμ ν΄κ²°
C++
#include <string>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;
long long solution(int n, vector<int> times) {
sort(times.begin(), times.end());
ll low = 0, high = times.back() * n;
while (low != high) {
ll mid = (low + high) / 2;
ll pos = 0;
for (int t: times) pos += mid / t;
if (pos >= n) high = mid;
else low = mid + 1;
}
return low;
}
κ°λ₯ν μκ°μ μ΄λΆ νμμ ν΅ν΄ ꡬν©λλ€.
1) μ²μ λ²μλ [0, κ°μ₯ μ€λ 걸리λ μ¬μ¬ μκ° * n] μΌλ‘ μ€μ ν©λλ€.
2) κ°λ₯ν μκ°μ νμν©λλ€.
2-1) mid κ°μ κ΅¬ν΄ mid μκ° λ΄μ λͺ¨λ μ¬μ¬κ° μ§νλ μ μλμ§ νλ¨ν©λλ€.
2-2) μ΄λ, pos += mid / t λ κ° μ¬μ¬λ λ§λ€ λ°μ μ¬λλ€μ νλ¨ν©λλ€.
2-3) pos >= n , mid μκ°μΌλ‘ ꡬν μμ© μΈμ (pos)μ΄ nλ³΄λ€ ν¬κ±°λ κ°λ€λ©΄ (κ°λ₯μ± μλ μν) μ‘°κΈ λ μμ κ°μΌλ‘ μλν©λλ€. (high = mid)
2-4) else, mid μκ°μΌλ‘ ꡬν μμ© μΈμμ΄ nλͺ λ³΄λ€ λΆμ‘±νλ€λ©΄ λ ν° κ°μΌλ‘ μλν©λλ€.
'ETC > Algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
Programmers, μ§κ²λ€λ¦¬ (2) | 2021.12.10 |
---|---|
Programmers, 보νμ μ²κ΅ (2) | 2021.12.08 |
programmers, λ¨μμΉ΄λ©λΌ (0) | 2021.12.03 |
Programmers, μ¬ μ°κ²°νκΈ° (2) | 2021.12.02 |
Programmers, λ¨μ²΄μ¬μ§ μ°κΈ° (0) | 2021.12.02 |
Backend Software Engineer
Gyeongsun Park