Algorithm πŸ§‘πŸ»‍πŸ’»/ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€(Programmers)

[c++] ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ - μ΅œλŒ€κ³΅μ•½μˆ˜μ™€ μ΅œμ†Œκ³΅λ°°μˆ˜( Level1)

dkswnkk 2021. 11. 8. 19:51

문제

 

μ½”λ”©ν…ŒμŠ€νŠΈ μ—°μŠ΅ - μ΅œλŒ€κ³΅μ•½μˆ˜μ™€ μ΅œμ†Œκ³΅λ°°μˆ˜

두 수λ₯Ό μž…λ ₯λ°›μ•„ 두 수의 μ΅œλŒ€κ³΅μ•½μˆ˜μ™€ μ΅œμ†Œκ³΅λ°°μˆ˜λ₯Ό λ°˜ν™˜ν•˜λŠ” ν•¨μˆ˜, solution을 μ™„μ„±ν•΄ λ³΄μ„Έμš”. λ°°μ—΄μ˜ 맨 μ•žμ— μ΅œλŒ€κ³΅μ•½μˆ˜, κ·Έλ‹€μŒ μ΅œμ†Œκ³΅λ°°μˆ˜λ₯Ό λ„£μ–΄ λ°˜ν™˜ν•˜λ©΄ λ©λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄ 두 수 3, 12의

programmers.co.kr

 

μ½”λ“œ

#include <string>
#include <vector>
#include <iostream>



using namespace std;

int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
vector<int> solution(int n, int m) {
    vector<int> answer;

    int inp = gcd(n,m);
    answer.push_back(inp);
    answer.push_back(n*m/inp);
    return answer;
}

 

풀이

μœ ν΄λ¦¬λ“œ 호제 μ•Œκ³ λ¦¬μ¦˜ 기법을 μ‚¬μš©ν•˜λ©΄ μ†μ‰½κ²Œ ν’€ 수 μžˆλŠ” λ¬Έμ œμ˜€μŠ΅λ‹ˆλ‹€.