[BOJ/백준][Gold5] 1188 : 음식 평론가 (C++)

 

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

1188번: 음식 평론가

 

 

[난이도] Gold5
[유형] 수학

[풀이]
N개의 소시지를 이어붙힌 뒤에 M등분을 해줘야 한다.

M-1번은 잘라야 하지만, 이어붙힌 소시지는 이미 N-1번 잘려있고 이 잘린 부분이
우리가 잘라야 하는 M-1번 자르는 부분과 겹칠 수 있으므로 이만큼은 M-1에서 빼줘야한다.
겹치는 부분은 (N과 M의 최대공약수)-1 이므로 정답은 M-1-(gcd(N,M)-1) = M-gcd(N,M) 이다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M;
int gcd(int a,int b){
    if(a>b) swap(a,b);
    while(a>0){
        int c = b%a;
        b=a;
        a=c;
    }
    return b;
}
int main(){
    scanf("%d%d",&N,&M);
    printf("%d",M-gcd(N,M));
} 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1188.cpp