< 백준 BaekJoon : 1934번 최소공배수 > C++

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

풀이

아주 Optimal한 풀이는 아닌 것 같지만.

 

기본 적인 컨셉은 numA와 numB가 있을 때, 

6과 10을 예시로 들면

 

6 < 10 이니

 

6에 2를 곱해준다

 

12 > 10 이니

 

10에 2를 곱해준다

 

12 < 20 이니

 

6에 앞서보다 1큰 3을 곱해준다.

 

6 * 3 < 10 * 2  => 18 < 20 이니

 

6에 앞서보다 1큰 4를 곱해준다.

 

6 *  4 < 10 * 2 => 24 > 20 이니

 

10에 앞서보다 1큰 3을 곱해준다

 

6 *4 < 10 * 3 => 24 < 30 이니

 

6에 앞서보다 1큰 5를 곱해준다.

 

6 * 5 = 10 * 3 => 30 = 30

 

이렇게 하면 각 수에 곱해주는 factor 두개를 점점 늘려가는 식으로 최소공배수를 찾을 수 있다.

 

#include<iostream>
#include<vector>
using namespace std;

int find(int a, int b){
  int factorA = 1;
  int factorB = 1;

  int mulA = a;
  int mulB = b;
  if(a == b){ return a; }

  int z;
  if (a > b){ z = a;}
  else { z = b; }

  while(mulA != mulB){
    if(mulA == mulB){ return mulA; }
    else if(mulA > mulB) factorB++;
    else if (mulA < mulB) factorA++;
    
    if(mulA > mulB){
      mulB = b * factorB;
    }
    else{
      mulA = a * factorA;
    }
  }
  return mulA;
}

int main() {
  int num;
  int numA, numB;
  cin >> num;
  
  for(int i=0; i< num; i++){
    cin >> numA >> numB;
    cout << find(numA,numB) << endl;
  }
  
}

 

 

진짜 어렵지 않은 문제였는데, 특히 이 문제 푸는게 유독 오래걸렸다.

 

아직 알고리즘은 너무 못한다.