[C++백준 1145번:적어도 대부분의 배수]

문제링크

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

1145번: 적어도 대부분의 배수

 

문제

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

출력

첫째 줄에 적어도 대부분의 배수를 출력한다.

 

해석

입력받은 5개의 수를 어떤 수(N)에 대해 mod연산을 진행하여 나온 결과가 0이라면 해당 수는 어떤수(N)를 나누는 수다.

따라서 어떤 수(N)를 나누는 수가 3개 이상이라면 N은 적어도 대부분의 배수가 된다.

1부터 어떤 수를 나누는 수가 3개 이상일 때까지 반복한다.

코드

#include <iostream>
using namespace std;
 
int main() {
    int n;
    int divisor[5];
 
    // 입력
    for (int i = 0; i < 5; i++) {
        cin >> n;
        divisor[i] = n;
    }
 
    int result = 1;
    int count = 0;
    while (true) {
        for (int i = 0; i < 5; i++) {
            if (result % divisor[i] == 0) {    // MOD==0이면 나눠지는 수 +
                count++;
            }
            if (count >= 3) {        // 나눠지는 수가 3개 이상이면 종료
                cout << result;
                return 0;
            }
        }
        result++;
        count = 0;
    }
 
}

 

Memo

이렇게 풀어도 효율적인지 모르겠다. 라는 생각을 가지고 풀었는데 이 문제도 브루트포스 알고리즘을 사용하여 푸는 문제였다. 알맞게 잘 푼 것 같다. 이제 조금은 브루트푸스 알고리즘에 익숙해진 느낌이다.