[백준] 5618번 공약수 / C++ Java

문제 : https://www.acmicpc.net/problem/5618

C++

#include<iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,a,b,c;
    cin >> n;

    if(n==2) {
        cin >> a >> b;
        for(int i = 1; i <= max(a,b); i++) {
            if(a % i == 0 && b % i == 0) {
                cout << i << endl;
            }
        }
    }
    else{
        cin >> a >> b >> c;
        int d = max(a,b);
        for(int i = 1; i <= max(d,c); i++) {
            if(a % i == 0 && b % i == 0 && c % i == 0) {
                cout << i << endl;
            }
        }
    }
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        if(n==2) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            for(int i = 1; i <= Math.max(a,b); i++) {
                if(a % i == 0 && b % i == 0) {
                    bw.write(i + "\n");
                }
            }
        }
        else if(n==3) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Math.max(a,b);
            for(int i = 1; i <= Math.max(c,d); i++) {
                if(a % i == 0 && b % i == 0 && c % i == 0) {
                    bw.write(i + "\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

문제풀이

• n이 2 또는 3이기 때문에, 먼저 2와 3일 때로 구분한다. 2일 때는 a,b 두 개 입력받고 max(a,b)까지 i 돌려서 공약수를 찾는다. 3일 때는 a,b,c 세 개 입력받고, max(a,b)값과 c 값의 max 값까지 i 돌려서 공약수 찾는다.

Comment

• 처음에는 for문의 범위를 10^8까지 해서 모두 비교했는데, 시간복잡도가 너무 컸다. 그래서 max 함수를 사용해 시간복잡도를 줄였다.