Problem Solving/BOJ & Programmers

[BOJ] 1654번: λžœμ„  자λ₯΄κΈ°

geum 2024. 9. 18. 22:59

✏️문제

μ§‘μ—μ„œ μ‹œκ°„μ„ λ³΄λ‚΄λ˜ μ˜€μ˜μ‹μ€ λ°•μ„±μ›μ˜ 뢀름을 λ°›κ³  κΈ‰νžˆ 달렀왔닀. 박성원이 μΊ ν”„ λ•Œ μ“Έ N개의 λžœμ„ μ„ λ§Œλ“€μ–΄μ•Ό ν•˜λŠ”λ° λ„ˆλ¬΄ λ°”λΉ μ„œ μ˜μ‹μ΄μ—κ²Œ 도움을 μ²­ν–ˆλ‹€.

이미 μ˜€μ˜μ‹μ€ 자체적으둜 K개의 λžœμ„ μ„ 가지고 μžˆλ‹€. κ·ΈλŸ¬λ‚˜ K개의 λžœμ„ μ€ 길이가 μ œκ°κ°μ΄λ‹€. 박성원은 λžœμ„ μ„ λͺ¨λ‘ N개의 같은 길이의 λžœμ„ μœΌλ‘œ λ§Œλ“€κ³  μ‹Άμ—ˆκΈ° λ•Œλ¬Έμ— K개의 λžœμ„ μ„ μž˜λΌμ„œ λ§Œλ“€μ–΄μ•Ό ν•œλ‹€. 예λ₯Ό λ“€μ–΄ 300cm 짜리 λžœμ„ μ—μ„œ 140cm 짜리 λžœμ„ μ„ 두 개 μž˜λΌλ‚΄λ©΄ 20cmλŠ” 버렀야 ν•œλ‹€. (이미 자λ₯Έ λžœμ„ μ€ 뢙일 수 μ—†λ‹€.)

편의λ₯Ό μœ„ν•΄ λžœμ„ μ„ 자λ₯΄κ±°λ‚˜ λ§Œλ“€ λ•Œ μ†μ‹€λ˜λŠ” κΈΈμ΄λŠ” μ—†λ‹€κ³  κ°€μ •ν•˜λ©°, 기쑴의 K개의 λžœμ„ μœΌλ‘œ N개의 λžœμ„ μ„ λ§Œλ“€ 수 μ—†λŠ” κ²½μš°λŠ” μ—†λ‹€κ³  κ°€μ •ν•˜μž. 그리고 자λ₯Ό λ•ŒλŠ” 항상 μ„Όν‹°λ―Έν„° λ‹¨μœ„λ‘œ μ •μˆ˜κΈΈμ΄λ§ŒνΌ 자λ₯Έλ‹€κ³  κ°€μ •ν•˜μž. Nκ°œλ³΄λ‹€ 많이 λ§Œλ“œλŠ” 것도 N개λ₯Ό λ§Œλ“œλŠ” 것에 ν¬ν•¨λœλ‹€. μ΄λ•Œ λ§Œλ“€ 수 μžˆλŠ” μ΅œλŒ€ λžœμ„ μ˜ 길이λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

 

πŸ€– μž…μΆœλ ₯ μ˜ˆμ‹œ

 

🧐 λ‚œμ΄λ„/μ†Œμš” μ‹œκ°„

  • λ‚œμ΄λ„: solved.ac κΈ°μ€€ S2
  • μ†Œμš” μ‹œκ°„: μΈ‘μ • X

 

πŸ’‘ν’€μ΄

보자마자 브루트포슀 μƒκ°ν–ˆλŠ”λ° λ„ˆλ¬΄ λ¬΄μ‹ν•œ 방법인 것 κ°™μ•„μ„œ μ•Œκ³ λ¦¬μ¦˜ λΆ„λ₯˜ λ΄€λ”λ‹ˆ '이뢄 탐색', 'λ§€κ°œλ³€μˆ˜ 탐색'이더라. κ±°κΈ°μ„œλΆ€ν„° μ΄ν•΄ν•˜μ§€ λͺ»ν–ˆκΈ° λ•Œλ¬Έμ—,, κ³΅λΆ€ν•œλ‹€λŠ” λ§ˆμΈλ“œλ‘œ 문제λ₯Ό 바라봀닀.

 

이런 건 μ§„μ§œ ν‰μ†Œμ— μœ ν˜•μ„ μ•Œκ³  μžˆμ–΄μ•Ό μ–΄λ–»κ²Œ ν’€μ–΄μ•Ό 할지가 λ°”λ‘œλ°”λ‘œ λ– μ˜€λ₯Ό λ“―

 

일단 ꡬ해야 ν•˜λŠ” κ°’λΆ€ν„° ν™•μΈν•΄λ³΄μž.

 

⭐ TO DO: μ˜€μ˜μ‹μ΄ 가지고 μžˆλŠ” K개의 λžœμ„ μ„ λͺ¨λ‘ 같은 길이둜 μž˜λΌμ„œ N개의 λžœμ„ μ„ λ§Œλ“€ λ•Œ, ν•œ λžœμ„ μ˜ μ΅œλŒ€ 길이 κ΅¬ν•˜κΈ°

 

πŸ‘©‍🏫 μ™œ λ§€κ°œλ³€μˆ˜ 탐색?

λ§€κ°œλ³€μˆ˜ 탐색 κ°œλ…μ„ μ—¬κΈ° 같이 적으면 λ„ˆλ¬΄ 글이 μ§€μ €λΆ„ν•΄μ§ˆ 것 κ°™μ•„μ„œ κ°œλ…μ€ λ‹€λ₯Έ κΈ€μ—μ„œ μ λŠ” 걸둜..!

일단 λ§€κ°œλ³€μˆ˜ 탐색 μœ ν˜•μ€ μ•„λž˜ 두 가지 쑰건을 λ§Œμ‘±ν•΄μ•Ό ν•œλ‹€.

 

1) 졜적의 κ°’(μ΅œλŒ€ λ˜λŠ” μ΅œμ†Œ)을 μ°ΎλŠ” λ¬Έμ œμΈκ°€?

2) κ²°μ • 문제(예 λ˜λŠ” μ•„λ‹ˆμ˜€λ‘œλ§Œ λ‹΅ν•  수 μžˆλŠ” 문제)둜 λ³€ν™˜ κ°€λŠ₯ν•œκ°€?

 

이 λ¬Έμ œκ°€ λ§€κ°œλ³€μˆ˜ 탐색 μœ ν˜•μ— μ†ν•œλ‹€λŠ” 것은 μ € 쑰건듀을 λ§Œμ‘±ν–ˆλ‹€λŠ” λœ»μ΄λ‹ˆκΉŒ μ–΄λ–€ 뢀뢄이 각 쑰건에 ν•΄λ‹Ήν•˜λŠ”μ§€ 보면

 

1) 졜적의 κ°’(μ΅œλŒ€ λ˜λŠ” μ΅œμ†Œ)을 μ°ΎλŠ” λ¬Έμ œμΈκ°€? → λžœμ„ μ΄ N개둜 μž˜λ Έμ„ λ•Œ ν•œ λžœμ„ μ˜ μ΅œλŒ€ 길이λ₯Ό κ΅¬ν•˜λŠ” 문제 βœ…

2) κ²°μ • 문제둜 λ³€ν™˜ κ°€λŠ₯ν•œκ°€? → λžœμ„ μ„ xxx 길이둜 μž˜λžμ„ λ•Œ N개 λ‚˜μ˜΄? 무쑰건 닡은 Yes or No βœ…

 

λΌλŠ” 결둠이 λ‚˜μ˜€κΈ° λ•Œλ¬Έμ— 이 λ¬Έμ œλŠ” λ§€κ°œλ³€μˆ˜ νƒμƒ‰μœΌλ‘œ ν’€ 수 μžˆλ‹€!

 

πŸ‘¨‍🏫 이뢄 탐색과 λ§€κ°œλ³€μˆ˜ νƒμƒ‰μ˜ 관계?

λ‚΄κ°€ μ΄ν•΄ν•œ λ°”+μ•„μ£Ό κ°„λ‹¨ν•˜κ²Œ λ§ν•˜λ©΄ 이뢄 탐색 = λ§€κ°œλ³€μˆ˜ 탐색 문제λ₯Ό ν’€κΈ° μœ„ν•΄ μ“°λŠ” 맀우 λΉ λ₯Έ μ•Œκ³ λ¦¬μ¦˜μΈλ°, ν˜Ήμ‹œλ‚˜ 잘λͺ»λœ 지식을 동넀방넀 적어둔 것이라면 μ–Έμ œλ“ μ§€ λŒ“κΈ€ λ‹¬μ•„μ£Όμ„Έμš”!

 

πŸ’» μ½”λ“œ

import sys

input = sys.stdin.readline

K, N = map(int, input().split())

ran = []

for _ in range(K):
    ran.append(int(input()))

start, end = 1, max(ran)

while start <= end:
    mid = (start+end) // 2  # 기쀀이 λ˜λŠ” 길이
    
    num = 0 # λΆ„ν• λœ λžœμ„  개수
    
    for item in ran:
        num += (item//mid)
    
    if num >= N:
        start = mid+1
    else:
        end = mid-1

print(end)

 

 

이뢄 탐색을 써야 ν•˜λŠ” 문제λ₯Ό 보면 항상 μ•Œκ³ λ¦¬μ¦˜ μžμ²΄λŠ” 어렡지 μ•Šμ€λ°, 이뢄 νƒμƒ‰μœΌλ‘œ ν’€μ–΄μ•Ό ν•˜λŠ”κ΅¬λ‚˜ 라고 κΉ¨λ‹«λŠ” 게 λ„ˆλ¬΄ μ–΄λ €μš΄ 것 κ°™λ‹€. μ €λŸ° 것도 λ‹€ 내곡 λΆ€μ‘±μ˜ μ΄μœ κ² μ§€ κ»„ κ»„