[Programmers] λ©μ©‘ν μ¬κ°ν
βΆ λ¬Έμ : https://programmers.co.kr/learn/courses/30/lessons/62048
μ½λ©ν μ€νΈ μ°μ΅ - λ©μ©‘ν μ¬κ°ν
κ°λ‘ κΈΈμ΄κ° Wcm, μΈλ‘ κΈΈμ΄κ° HcmμΈ μ§μ¬κ°ν μ’ μ΄κ° μμ΅λλ€. μ’ μ΄μλ κ°λ‘, μΈλ‘ λ°©ν₯κ³Ό νννκ² κ²©μ ννλ‘ μ μ΄ κ·Έμ΄μ Έ μμΌλ©°, λͺ¨λ 격μμΉΈμ 1cm x 1cm ν¬κΈ°μ λλ€. μ΄ μ’ μ΄λ₯Ό 격μ μ μ
programmers.co.kr
βΆ μ½λ :
function solution(w, h) {
const total = w * h;
const g = gcd(w, h); // g μ¦, μ΅λ곡μ½μλ λκ°μ μΌλ‘ λλμμλ λ°λ³΅λλ μ¬κ°νννκ° λ±μ₯νλ νμμ΄λ€.
const miniSquare = w/g + h/g - 1; // κ°κ°μ μμ μ¬κ°νμ κ°λ‘λ₯Ό gλ‘ λλκ°κ³Ό μΈλ‘λ₯Ό gλ‘ λλκ°μμ 1(μ€λ³΅ν΄μ μλ₯΄λ μ¬κ°ν)μ λΊ κ°λ§νΌ μ¬κ°νμ μ§μ΄λ€.
return total - (g * miniSquare);
}
function gcd(a,b){
if(b === 0){
return a;
}else{
return gcd(b, a % b);
}
}
βΆ λ¬Έμ νμ΄ :
- ν΄λΉ λ¬Έμ λ 'λ©μ©‘ν μ¬κ°ν νμ΄' λ₯Ό μ°Έκ³ νμ¬ νμ΄νμλ€.
1. μ 체 μ¬κ°νμμ μ리λ μ¬κ°νμ μλ₯Ό μΈμ΄μΌ νλ€. (μ΄λ, μ 체μ¬κ°νμ μ§μ¬κ°νμ΄λΌλ μ μ μ‘°κ±΄μ΄ λ¬Έμ μ μλ€.)
2. μ 체 μ¬κ°νμμ μ리λ μ¬κ°ν(μ리λ μμ)μ λ°λ³΅λλ ννλ₯Ό κ°μ§λλ°, μ΄λ λ°λ³΅λλ νμλ GCD(μ΅λ곡μ½μ) λ² λ±μ₯νλ€.
3. μΆκ°μ μΌλ‘ μ리λ μμμ μμ μ¬κ°νμ΄ μ΅λ곡μ½μ λ² λ±μ₯νλ€λ©΄ νλμ μμ μμ μ¬κ°ν λ΄λΆμμ μ리λ μ¬κ°νμ κ°μλ μ΄λ»κ² ꡬν κΉ?
- μμ μ¬κ°νμ ν¬κΈ°λ (w // g) * (h // g) μ΄λ€. μ΄λ κ°κ°μ μ¬κ°νμ λν΄ λκ°μ μ κ·Έμμλ (μμ μ¬κ°νμ κ°λ‘) κ°, (μμ μ¬κ°νμ μΈλ‘) κ° μ© λλλ€. νμ§λ§ μ΄λ κ°λ‘μ μΈλ‘μ λν΄ μ€λ³΅μΌλ‘ μΉ΄μ΄ν νλ μΉΈ(μ²μ μμμΉΈ) μ λν 1μ λΉΌμ£Όμ΄μΌνλ€.
4. μ§κΈ κΉμ§μ λ§μ μ 리ν΄λ³΄λ©΄ μ 체 μ¬κ°νμ ν¬κΈ° (w * h) μμ gcd(μμ μ¬κ°νμ λ±μ₯ νμ) * miniSquare(μμ μ¬κ°νμμ λκ°μ μ μν΄ μ μΈλλ μ¬κ°νμ μ)λ₯Ό λΉΌμ£Όμ΄μΌ νκ³ miniSquareμ μλ "(w / g) + (h /g) - 1" μ΄ λλ€λ κ²μ΄λ€.
5. λ°λΌμ μ 체 μμ `(w * h) - gcd * (w/g + h/g - 1)` μ΄ λμ΄μΌ νλ€λ μλ―Έμ΄λ€.
6. gcd() ν¨μλ 'μ ν΄λ¦¬λ νΈμ ' λ₯Ό μ°Έκ³ ν΄ κ΅¬ννμμΌλ©° κ°κ°μ μ‘°ν©νμ¬ κ²°κ³Όλ₯Ό μΆλ ₯ν΄μ£Όλ©΄ λλ λ¬Έμ μλ€.