[Java] SWEA 8659번 GCD

SW Expert Academy

---

풀이

DP를 사용해서 해결했습니다.

 

문제에서 A가 가장 작으며 그런 조합이 여러 가지인 경우 B가 가장 작은 조합을 선택하면 된다는 조건이 있고 GCD(a, b)일 때,테스트 케이스에서 주어진 K = 1부터 해보면

 

K = 1

GCD(2, 1) = GCD(1, 2 % 1) = GCD(1, 0) = 1

 

K = 2

GCD(3, 2) = GCD(2, 3 % 2) = GCD(2, 1) = (K = 1)인 경우가 반복

 

K = 3

GCD(5, 3) = GCD(3, 5 % 3) = GCD(3, 2) = (K = 2)인 경우가 반복

 

...

 

K = n

GCD((n - 1의 a) + (n - 1의 b), n - 1의 a) = (K = n - 1)인 경우가 반복하는 형태가 됩니다.

 

즉,

memo[i][0] = memo[i - 1][0] + memo[i - 1][1]

memo[i][1] = memo[i - 1][0]

가 됩니다.

 

이때, K가 90에 가까워질수록 수가 매우 커질 수 있으므로 long 자료형으로 해야 합니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
	public static int K;
	public static long[][] memo = new long[91][2];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		
		memo[1][0] = 2;
		memo[1][1] = 1;
		for (int i = 2; i <= 90; ++i) {
			memo[i][0] = memo[i - 1][0] + memo[i - 1][1];
			memo[i][1] = memo[i - 1][0];
		}

		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; ++tc) {
			K = Integer.parseInt(br.readLine());
			
			sb.append("#").append(tc).append(" ")
			  .append(memo[K][0]).append(" ").append(memo[K][1])
			  .append("\n");
		}
		
		System.out.println(sb);
	}
}

---

pyo7410/Algorithm