[백준] 1850번: 최대공약수

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

1850번: 최대공약수

 

---

문제설명

간단한 최대공약수 구하는 문제이지만, 만약 입력이 3 4면 111과 1111의 최대공약수를 구하는 문제이다.

 

코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long a = sc.nextLong();
		long b = sc.nextLong();
		long res = gcd(a, b);
		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < res; i++) {
			sb.append(1);
		}

		System.out.println(sb);
	}

	static long gcd(long a, long b) {
		if (a % b == 0) {
			return b;
		}

		return gcd(b, a % b);
	}
}

코드설명

일단 최대공약수를 구하는 함수를 작성한다.

이 문제는 입력이 크기 때문에, 리턴할 자료형을 long으로 해놓고, 인자들도 long으로 한다.

그리고  첫 번째로 입력한 수 % 두 번째로 입력한 수가 0이면 두 번째로 입력한 수가 최대공약수가 되는 규칙이 있으므로 조건문 하나를 작성한다.

최대공약수는 두 개의 자연수 a, b에 대해서 b와 a % b의 값의 최대공약수와 같으므로 리턴값으로는 재귀로 이 규칙을 리턴시킨다.StringBuilder를 사용해서 res만큼의 for문을 돌려 StringBuilder에 1을 append 시킨다.그럼 정답과 맞게 출력이 나온다.