[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - N개의 μ΅œμ†Œκ³΅λ°°μˆ˜(C++)

2023. 7. 3. 11:01Β·πŸ–₯️ Study Note/Coding Test

https://school.programmers.co.kr/learn/courses/30/lessons/12953

문제 μ„€λͺ…

두 수의 μ΅œμ†Œκ³΅λ°°μˆ˜(Least Common Multiple)λž€ μž…λ ₯된 두 수의 배수 쀑 곡톡이 λ˜λŠ” κ°€μž₯ μž‘μ€ 숫자λ₯Ό μ˜λ―Έν•©λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄ 2와 7의 μ΅œμ†Œκ³΅λ°°μˆ˜λŠ” 14κ°€ λ©λ‹ˆλ‹€. μ •μ˜λ₯Ό ν™•μž₯ν•΄μ„œ, n개의 수의 μ΅œμ†Œκ³΅λ°°μˆ˜λŠ” n 개의 μˆ˜λ“€μ˜ 배수 쀑 곡톡이 λ˜λŠ” κ°€μž₯ μž‘μ€ μˆ«μžκ°€ λ©λ‹ˆλ‹€. n개의 숫자λ₯Ό 담은 λ°°μ—΄ arr이 μž…λ ₯λ˜μ—ˆμ„ λ•Œ 이 μˆ˜λ“€μ˜ μ΅œμ†Œκ³΅λ°°μˆ˜λ₯Ό λ°˜ν™˜ν•˜λŠ” ν•¨μˆ˜, solution을 μ™„μ„±ν•΄ μ£Όμ„Έμš”.

μ œν•œ 사항

  • arr은 길이 1이상, 15μ΄ν•˜μΈ λ°°μ—΄μž…λ‹ˆλ‹€.
  • arr의 μ›μ†ŒλŠ” 100 μ΄ν•˜μΈ μžμ—°μˆ˜μž…λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

arr result
[2,6,8,14] 168
[1,2,3] 6

λ‚΄ 풀이

μ΅œμ†Œκ³΅λ°°μˆ˜ ⇒ A * B / μ΅œλŒ€κ³΅μ•½μˆ˜

μ΅œλŒ€κ³΅μ•½μˆ˜ ⇒ 큰 수 Aλ₯Ό μž‘μ€ 수 B둜 λ‚˜λˆ„μ–΄ λ–¨μ–΄μ§€λ©΄, A, B의 μ΅œλŒ€κ³΅μ•½μˆ˜λŠ” B, Aλ₯Ό B둜 λ‚˜λˆ„μ—ˆμ„ λ•Œ λ‚˜λ¨Έμ§€κ°€ R이면, A, B의 μ΅œλŒ€κ³΅μ•½μˆ˜λŠ” Rκ³Ό B의 μ΅œλŒ€κ³΅μ•½μˆ˜μ™€ κ°™λ‹€.

μ—¬λŸ¬ 수의 μ΅œμ†Œ 곡배수λ₯Ό κ΅¬ν•˜λ €λ©΄ 2개λ₯Ό λ¬Άμ–΄ μ΅œμ†Œ 곡배수λ₯Ό κ΅¬ν•˜κ³  κ·Έ μ΅œμ†Œ κ³΅λ°°μˆ˜μ™€ λ‹€μŒ 수의 μ΅œμ†Œ 곡배수λ₯Ό κ΅¬ν•˜λŠ” μ‹μœΌλ‘œ μ§„ν–‰ν•˜λ©΄ λœλ‹€.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int GCD(int a, int b)
{
    int imax = max(a,b);
    int imin = min(a,b);
    
    int r = imax % imin;
    
    if( r == 0)
        return imin;
    else 
        return GCD(imin, r);
}

int solution(vector<int> arr) {
    int answer = arr[0];
    
    for(int i = 1; i < arr.size(); i++)
    {
        int gcd = GCD(answer, arr[i]);
        int lcm = answer * arr[i] / gcd;
        answer = lcm;
    }
    return answer;
}
μ €μž‘μžν‘œμ‹œ λΉ„μ˜λ¦¬ λ³€κ²½κΈˆμ§€ (μƒˆμ°½μ—΄λ¦Ό)

'πŸ–₯️ Study Note > Coding Test' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 배달(C++)  (0) 2023.07.10
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 두 큐 ν•© κ°™κ²Œ λ§Œλ“€κΈ°(C++)  (0) 2023.07.04
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 점프와 μˆœκ°„ 이동(C++)  (0) 2023.06.30
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 과제 μ§„ν–‰ν•˜κΈ°(C++)  (0) 2023.06.29
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - μ˜ˆμƒ λŒ€μ§„ν‘œ(C++)  (0) 2023.06.28
'πŸ–₯️ Study Note/Coding Test' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 배달(C++)
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 두 큐 ν•© κ°™κ²Œ λ§Œλ“€κΈ°(C++)
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 점프와 μˆœκ°„ 이동(C++)
  • [ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - 과제 μ§„ν–‰ν•˜κΈ°(C++)
Beankong_
Beankong_
μ£Όλ‹ˆμ–΄ ν΄λΌμ΄μ–ΈνŠΈ ν”„λ‘œκ·Έλž˜λ¨Έ 곡뢀 기둝
  • Beankong_
    Beankong's Devlog
    Beankong_
  • 전체
    였늘
    μ–΄μ œ
    • 전체 κΈ€ (146)
      • β›… Daily (0)
      • πŸ–₯️ Study Note (2)
        • C++ (1)
        • Unreal Engine (5)
        • Coding Test (123)
        • Design Patteren (5)
        • VCS (Git..) (1)
        • Server (1)
      • 🧭 Devlog (8)
        • μ˜€λ‹΅λ…ΈνŠΈ (4)
        • UE5 GameLift Server Test Project (1)
        • TIL (3)
  • hELLOΒ· Designed Byμ •μƒμš°.v4.10.3
Beankong_
[ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€]level.2 - N개의 μ΅œμ†Œκ³΅λ°°μˆ˜(C++)
μƒλ‹¨μœΌλ‘œ

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”