πŸ“ PROGRAMMERS - λ©€μ©‘ν•œ μ‚¬κ°ν˜•

문제

PROGRAMMERS Level 2 - λ©€μ©‘ν•œ μ‚¬κ°ν˜•

μ ‘κ·Ό 방법

λ‚΄κ°€ 처음 κ΅¬ν˜„ν–ˆλ˜ ν’€μ΄λŠ” (0,0)(0, 0)κ³Ό (w,h)(w, h)λ₯Ό μž‡λŠ” μ§μ„ μ˜ 방정식을 λ§Œλ“€μ–΄ kkκ°€ μžμ—°μˆ˜ 일 λ•Œ y=ky = k일 λ•Œμ˜ xxμ’Œν‘œλ₯Ό ꡬ해 μ œμ™Έν•΄μ•Όν•˜λŠ” μ‚¬κ°ν˜•μ„ κ΅¬ν–ˆλ‹€. ν•˜μ§€λ§Œ μ΄λ ‡κ²Œ ν’€λ©΄ μ‹œκ°„μ΄ˆκ³Όκ°€ λ‚œλ‹€.

κ²°κ΅­ 풀지 λͺ»ν•΄μ„œ μŠˆνΌμ§±μ§±λ‹˜μ˜ 풀이λ₯Ό μ°Έκ³ ν–ˆλ‹€. μ„€λͺ…을 정말 잘 ν•΄μ£Όμ…”μ„œ λ‚΄ μ„€λͺ…λ³΄λ‹€λŠ” 이 λΆ„μ˜ μ„€λͺ…을 μ½λŠ” 것을 더 μΆ”μ²œν•˜λ‹€!

μ„€λͺ…

normal-square

λ„ˆλΉ„κ°€ 4이고 높이가 6인 μ‚¬κ°ν˜•μ΄ μžˆλ‹€. 이 μ‚¬κ°ν˜•μ˜ μ™Όμͺ½ μ•„λž˜λ₯Ό (0,0)(0, 0)으둜 두고 (0,0)(0, 0)κ³Ό (4,6)(4, 6)을 μ§€λ‚˜λŠ” 선을 그리면 λ‹€μŒκ³Ό κ°™λ‹€. 이 선은 (0,0)(0, 0)κ³Ό (4,6)(4, 6)외에도 (2,3)(2, 3)도 μ§€λ‚œλ‹€.

이 λ•Œ 원점을 μ œμ™Έν•œ 직선이 μ§€λ‚˜λŠ” 점(= λΉ¨κ°„ μ‚¬κ°ν˜•)의 κ°œμˆ˜λŠ” 2개 즉, 4와 6의 μ΅œλŒ€κ³΅μ•½μˆ˜μž„μ„ μ•Œ 수 μžˆλ‹€.

κ²°λ‘ 

ww와 hh의 μ΅œλŒ€κ³΅μ•½μˆ˜κ°€ 1인 경우 직선이 μ§€λ‚˜λŠ” 점은 (0,0)(0, 0)κ³Ό (w,h)(w, h)μ™Έμ—λŠ” μ—†λ‹€. 즉 μ‚¬κ°ν˜• 전체가 λΉ¨κ°„ μ‚¬κ°ν˜•μ΄ λœλ‹€. 이 μ‚¬κ°ν˜•μ— λŒ€κ°μ„ μ„ 그리면 λ„ˆλΉ„μ™€ λ†’μ΄μ˜ 개수 만큼의 μ‚¬κ°ν˜•μ„ μ§€λ‚œλ‹€. 이 λ•Œ κ³΅ν†΅μœΌλ‘œ μ§€λ‚˜λŠ” μ‚¬κ°ν˜•μ΄ μžˆμœΌλ―€λ‘œ 1을 λΉΌλ©΄, μ œμ™Έλ˜λŠ” μ‚¬κ°ν˜•μ˜ κ°œμˆ˜λŠ” w+hβˆ’1w+h-1이 λœλ‹€.

ww와 hh의 μ΅œλŒ€κ³΅μ•½μˆ˜κ°€ 1보닀 클 λ•ŒλŠ” μ•žμ˜ μ˜ˆμ‹œμ²˜λŸΌ μ΅œλŒ€κ³΅μ•½μˆ˜μ˜ 개수만큼의 빨간색 μ‚¬κ°ν˜•μ΄ μ‘΄μž¬ν•œλ‹€. 이 λ•Œ 이 빨간색 μ‚¬κ°ν˜•μ˜ μ΅œλŒ€κ³΅μ•½μˆ˜λŠ” 1μ΄λ―€λ‘œ μ•žμ˜ 곡식을 μ΄μš©ν•˜μ—¬ λΉ¨κ°„ μ‚¬κ°ν˜• λ‚΄μ—μ„œ μ œμ™Έλ˜λŠ” μ‚¬κ°ν˜•μ˜ 개수λ₯Ό κ΅¬ν•˜κ³  빨간색 μ‚¬κ°ν˜•μ˜ 개수만큼 κ³±ν•΄μ£Όλ©΄ λœλ‹€. 즉, ww와 gg의 μ΅œλŒ€κ³΅μ•½μˆ˜κ°€ gcdgcd일 λ•Œ, μ œμ™Έλ˜λŠ” μ‚¬κ°ν˜•μ˜ κ°œμˆ˜λŠ” gcdβˆ—(w/gcd+h/gcdβˆ’1)=w+hβˆ’ggcd * (w/gcd + h/gcd - 1) = w + h - g이닀.

κ΅ν›ˆ

μ—¬λŸ¬ λͺ¨μ–‘μ˜ μ‚¬κ°ν˜•μ„ κ·Έλ €λ³΄λ©΄μ„œ κ·œμΉ™μ„ κ΅¬ν•˜λ € ν–ˆλŠ”λ° λˆˆμ— λ³΄μ΄λŠ” κ·œμΉ™μ΄ μ—†μ–΄μ„œ κ²°κ΅­ λ‹€λ₯Έ λΆ„μ˜ 풀이λ₯Ό μ°Έκ³ ν•˜μ˜€λ‹€. μ•Œκ³ λ¦¬μ¦˜ 문제라기 λ³΄λ‹€λŠ” μˆ˜ν•™ λ¬Έμ œμ— κ°€κΉŒμš΄λ° μ—¬νƒœκΉŒμ§€ ν’€μ—ˆλ˜ μˆ˜ν•™ 문제 쀑 μ΅œλŒ€κ³΅μ•½μˆ˜μ™€ μ΅œμ†Œκ³΅λ°°μˆ˜λ₯Ό μ΄μš©ν•œ λ¬Έμ œλ“€μ΄ κ½€ μžˆμ—ˆλ‹€. λΉ„μŠ·ν•œ λ¬Έμ œκ°€ λ‚˜μ˜¨λ‹€λ©΄ μ΅œλŒ€κ³΅μ•½μˆ˜λ‚˜ μ΅œμ†Œκ³΅λ°°μˆ˜λ₯Ό μ˜μ‹¬ν•΄λ΄μ•Όκ² λ‹€.

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

import math

def solution(w,h):
    gcd = math.gcd(w, h)
    if gcd == 1:
        return w*h-(w+h-1)
    return w*h-(w+h-gcd)

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

GitHubInstagramAI Notebook