[BOJ C++] 백준 32653번: 흑백 요리사

 📚 문제

[BOJ C++] 백준 32653번: 흑백 요리사
https://www.acmicpc.net/problem/32653

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 두께가 x인 스테이크를 뒤집을 때는 반드시 x분만큼 구운 후 뒤집어야 하므로, 각 스테이크의 적어도 최소공배수만큼의 시간이 필요하다.
• N개의 스테이크가 모두 even 하게 익은 상태가 되려면 모든 스테이크의 최소공배수를 각 스테이크의 두께로 나누었을 때의 몫이 짝수여야한다.
• 최대공약수, 최소공배수를 구할 때는 유클리드 호제법을 사용한다. (아래 글 참고)
• 유클리드 호제법
• 이 문제에서는 3개 이상인 여러 수의 최대공약수와 최소공배수를 구해야 한다. 이 경우에는 먼저 2개의 최대공약수와 최소공배수를 구한 후, 구한 최소공배수와 새로운 수의 최대공약수, 최소공배수를 구하는 과정을 반복하면 된다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int gcd(int n, int m) {
    if (n < m) swap(n, m);
    if (m == 0) return n;
    else
        return gcd(m, n % m);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
        int g = v[0];
        long long l = v[0];
        for (int i = 1; i < n; i++) {
        g = gcd(l, v[i]); // 최대공약수
        l *= v[i]; // 두 수의 곱
        l /= g; // 최소공배수
    }

    int mul = 1; // 최소공배수에 곱해줄 수.
    if (l % 2) mul++;  // 최소공배수의 배수 중 짝수여야함.
    int flag = 0;
    while(1) {
        for (int i = 0; i < n; i++) {
            int tmp = l * mul / v[i];
            //cout << "!"<< tmp << "\n";
            if((l*mul/v[i]) % 2) { // even 하지 않으면
                mul++; // 다음 배수 확인
                break;
            }
            if (i == n - 1) flag = 1;
        }
        if (flag) break;
    }

    cout << l * mul;
}