πŸ“ BOJ - 1둜 λ§Œλ“€κΈ°

문제

BOJ 1463번 : 1둜 λ§Œλ“€κΈ°

μ ‘κ·Ό 방법

μ •μˆ˜ NN이 μ£Όμ–΄μ§ˆ λ•Œ 이 NN에 λ‹€μŒμ˜ 연산을 가지고 11을 λ§Œλ“œλ €κ³  ν•  λ•Œ 연산을 μ‚¬μš©ν•˜λŠ” 횟수의 μ΅œμ†Œκ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€.

  • NN이 3으둜 λ‚˜λˆ„μ–΄ 떨어지면, 3으둜 λ‚˜λˆˆλ‹€.
  • NN이 2둜 λ‚˜λˆ„μ–΄ 떨어지면, 2둜 λ‚˜λˆˆλ‹€.
  • 1을 λΊ€λ‹€.

μ„€λͺ…

ν˜„μž¬μ— 집쀑해 숫자 66을 가지고 μƒκ°ν•΄λ³΄μž! 66을 λ§Œλ“€κΈ° μœ„ν•΄μ„œλŠ” 22에 3을 κ³±ν•˜κ±°λ‚˜, 33에 2λ₯Ό κ³±ν•˜κ±°λ‚˜, 55에 1을 λ”ν•΄μ•Όν•œλ‹€. 이제 22λ₯Ό λ§Œλ“€κΈ° μœ„ν•΄μ„œλŠ” 11에 2λ₯Ό κ³±ν•˜κ±°λ‚˜ 1을 λ”ν•΄μ•Όν•œλ‹€. 33은 11에 3을 κ³±ν•΄ λ§Œλ“€ 수 μžˆλ‹€. 55λŠ” 44에 1을 λ”ν•΄μ„œ λ§Œλ“€ 수 μžˆλ‹€.

μœ„μ˜ 과정을 μ‚΄νŽ΄λ³΄λ©΄ κ²°κ΅­ μ–΄λ–€ 숫자 NN을 λ§Œλ“€κΈ° μœ„ν•΄μ„œλŠ” κ·Έ μ „μ˜ 숫자λ₯Ό 가지고 연산을 ν•΄μ•Ό ν•œλ‹€. 즉, Nβˆ’1N-1에 1을 λ”ν•˜κ±°λ‚˜, N/2N/2에 2λ₯Ό κ³±ν•˜κ±°λ‚˜, N/3N/3에 3을 κ³±ν•΄μ•Όν•œλ‹€. κ·Έ μ „μ˜ μˆ«μžμ—μ„œμ˜ μ—°μ‚°μ˜ 합에 1을 λ”ν•˜μ—¬ 3κ°€μ§€μ˜ 각각 λ‹€λ₯Έ μ—°μ‚° 횟수λ₯Ό ꡬ할 수 μžˆλŠ”λ° κ·Έ 쀑 μ΅œμ†Œκ°’μ΄ μ—°μ‚° 횟수의 μ΅œμ†Œκ°’μ΄λ‹€.

κ²°λ‘ 

1λΆ€ν„° μ‹œμž‘ν•΄ μ–΄λ–€ 수 ii에 λ„λ‹¬ν•˜κΈ° μœ„ν•΄μ„œλŠ” λ‹€μŒμ˜ μ—°μ‚° 쀑 ν•˜λ‚˜λ₯Ό ν•΄μ•Ό ν•œλ‹€.

  • iβˆ’1i-1에 1을 λ”ν•œλ‹€.
  • iiκ°€ 2둜 λ‚˜λˆ„μ–΄λ–¨μ–΄μ§€λŠ” 경우, i/2i/2에 2λ₯Ό κ³±ν•œλ‹€.
  • iiκ°€ 3으둜 λ‚˜λˆ„μ–΄λ–¨μ–΄μ§€λŠ” 경우, i/3i/3에 3을 κ³±ν•œλ‹€.

각 숫자의 μ—°μ‚°ν•˜κΈ° μ „μ˜ 숫자의 μ—°μ‚° νšŸμˆ˜μ— 1을 λ”ν•΄μ„œ 3개의 μ—°μ‚° 쀑 κ°€μž₯ 적은 개수의 연산을 ν˜„μž¬ 숫자의 μ—°μ‚° 횟수둜 κ°±μ‹ ν•˜λ©΄ λœλ‹€. 이λ₯Ό μ ν™”μ‹μœΌλ‘œ λ‚˜νƒ€λ‚΄λ©΄ λ‹€μŒκ³Ό κ°™λ‹€. 이 λ•Œ sum[i]sum[i]λŠ” 숫자 ii에 μ˜€κΈ°κΉŒμ§€μ˜ μ΅œμ†Œ μ—°μ‚°νšŸμˆ˜μ΄λ‹€.

sum[i]=min(sum[iβˆ’1],sum[i//2],sum[i//3])+1sum[i] = min(sum[i-1], sum[i//2], sum[i//3])+1

κ΅ν›ˆ

μ²˜μŒμ— 11λΆ€ν„°κ°€ μ•„λ‹Œ NNλΆ€ν„° μ‹œμž‘ν–ˆλ‹€. 예λ₯Ό λ“€λ©΄ 문제 μ˜ˆμ‹œμ—μ„œ 3이 되기 μœ„ν•΄μ„œλŠ” 4μ—μ„œ 1을 λΉΌκ±°λ‚˜ 6을 2둜 λ‚˜λˆ„κ±°λ‚˜ 9λ₯Ό 3으둜 λ‚˜λˆ„κ±°λ‚˜ ν•˜λ©΄ λœλ‹€. ν•  수 μžˆμ„ 것 κ°™κΈ΄ν•œλ° λ³΅μž‘ν•΄μ Έμ„œ ν¬κΈ°ν–ˆλ‹€γ… γ… 

κ²°κ΅­ Newmoonλ‹˜μ˜ 풀이λ₯Ό μ°Έκ³ ν–ˆλŠ”λ° 1λΆ€ν„° μ‹œμž‘ν•˜λŠ” 것을 λ³΄μ•˜λ‹€. 사싀 1μ—μ„œ μ‹œμž‘ν•˜λ“  NNμ—μ„œ μ‹œμž‘ν•˜λ“  λ˜‘κ°™κΈ° λ•Œλ¬Έμ— μ–΄λŠ κ±Έ 해도 상관없닀. λ™μ κ³„νšλ²•μ—μ„œ 항상 ν˜„μž¬λ§Œ μƒκ°ν–ˆλŠ”λ° μ΄μ œλŠ” μ‹œμž‘μ λ„ κ³ λ €ν•΄μ•Όκ² λ‹€.

μ†ŒμŠ€ μ½”λ“œ

n = int(input())
table = [0] * (n+1)

for i in range(2, n+1):
  table[i] = table[i-1]+1

  if i%2 == 0:
    table[i] = min(table[i], table[i//2]+1)

  if i%3 == 0:
    table[i] = min(table[i], table[i//3]+1)

print(table[-1])

Written by@μ½”λ”©ν•˜λŠ”νŽ­κ·„
μ§€κΈˆμ€ ν•˜κ³  싢을 λ•Œλ§Œ κ³΅λΆ€ν•©λ‹ˆλ‹€πŸ€—

GitHubInstagramAI Notebook