[C] 코드업 문제풀이 2623번: 최대공약수 구하기

문제설명

두 정수 a, b를 입력받아서, a, b의 최대공약수를 출력하시오.

 

 

입력

정수 a, b가 공백으로 구분되어 입력된다.(1<=a,b<=10,000)

 

 

출력

a, b의 최대공약수를 출력한다.

 

 

입력예시

64 128

 

 

출력예시

64

 

---

#include <stdio.h>
int main(void){
    int a,b;
    int min=0;
    scanf("%d %d", &a, &b);
    for(int i=1;i<=a;i++){
        if(a%i==0&&b%i==0){
            min=i;
        }
        
    }
    printf("%d", min);
    return 0;
}

이 문제를 굉장히 꼬아서 생각했다. 어디에선지는 기억안나지만 16진수 문제였기 때문으로 기억한다. 그래서 그 형태로 구하는 것을 생각했던 것 같다. 그런데 그것이 아니였다. 최대공약수이기 때문에 둘다 나눠지는 것중 가장 큰 값만 구해주면 되는 것이다. 그렇기에 for문을 이용할 수 있다. i값을 대입해 나누어 지는지 계속 확인하고 나눠지는 값이 나올때마다 min값으로 교체해주면 되는 것이다. 나누어져야 한다는 두 조건을 만족하기 위해 &&를 이용한다. 그리고 계속 반복해서 끝나게 되면 printf를 이용해 min값을 출력해주면 된다.

기존 문제의 틀에 갇히지 말고 본래의 의미를 생각해보자!