[랜덤 마라톤] 퍼거슨과 사과(2942)

1. 문제 풀이 아이디어

• 최대 공약수를 활용하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int r = Integer.parseInt(stringTokenizer.nextToken());
        int g = Integer.parseInt(stringTokenizer.nextToken());
        int gcd = gcd(r, g);
        for (int i = 1; i * i <= gcd; i++) {
            if (gcd % i == 0) {
                stringBuilder.append(String.format("%d %d %d\n", i, r / i, g / i));
                if (gcd / i != i) {
                    stringBuilder.append(String.format("%d %d %d\n", gcd / i, r / gcd * i, g / gcd * i));
                }
            }
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }

    private static int gcd(int a, int b) {
        return a % b == 0 ? b : gcd(b, a % b);
    }
}

3. 정리

• 최대 공약수를 구하는 gcd 메서드를 구현한다.

• 두 수의 최대 공약수를 계산하여 gcd에 저장한다.

• gcd의 약수로 r과 g를 나누어 문제를 해결한다.