[SWEA] 8659. GCD

문제

의석이는 종강 기념 피자 파티를 열기 위해서 피자를 사러 왔다.

하지만 피자 가게 주인 동욱이는 피자를 순순히 판매하지 않는 사람이다.

돈 보다 문제 내는 것을 더 좋아하는 이상한 동욱이는 피자를 사러 온 의석이에게 3개의 시련을 부여했고, 모두 통과해야만 거래를 시작한다.

두 번째 관문에서는 GCD에 관련된 내용을 물어본다.
 

           GCD(a,0) = a
           GCD(a,b) = GCD(b, a%b)
 

GCD는 위와 같은 성질을 가진 함수이다.
 
동욱이가 원하는 것은 두 개의 숫자 A, B(A>B)를 찾는 것이다.
 
단, 이 두 개의 숫자에 대해서 GCD(A,B)를 실행하면 % 연산자가 총 K 번 수행된다는 사실을 알고 있다.
 
이러한 두 개의 숫자 조합 중에서 A가 가장 작으며 그런 조합이 여러 가지라면 B가 가장 작은 조합을 원한다.
 
예를 들어서, % 연산자가 3번 수행되는 조합은 (5, 3), (8, 3), (10, 6) 등이 있다.
 
그 중 원하는 조합은 (5, 3) 이 되는 것이다.
 
의석이를 도와서 K가 주어졌을 때, 관문 2의 정답을 구하는 프로그램을 작성하라.

 

풀이방법

동적 계획법(DP, Dynamic Programming)을 이용해 해결한다.

 

GCD(a, 0) = a,  GCD(a, b) = GCD(b, a%b)일 때, k번 수행하는 가장 작은 조합을 찾아야하므로

 

1부터 k를 만족하는 가장 작은 a, b부터 찾는다.

 

(k = 0) GCD(1, 0) = 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) = GCD(1, 0) = 1

 

(k = 3) GCD(5, 3) = GCD(3, 5 % 3) = GCD(3, 2) = GCD(2, 1) = GCD(1, 0) = 1

 

(k = 3) GCD(8, 5) = GCD(5, 8 % 5) = GCD(5, 3) = GCD(3, 2) = GCD(2, 1) = GCD(1, 0) = 1

 

k+1일 때, GCD(a,b) 나머지 연산을 한 번했을 때, GCD(a, b)는 k일 때, GCD(a, b)의 a, b와 같다.

 

 

따라서 아래와 같은 점화식을 찾을 수 있다.

 

a[k] = a[k-1] + b[k-1]

 

b[k] = a[k-1]

 

소스코드

package samsung;

import java.util.*;

public class s_8659 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int k = sc.nextInt();
			long[][] dp = new long[k][2];
			
			dp[0][0] = 2;
			dp[0][1] = 1;
			
			for(int i = 1; i < k; i++) {
				dp[i][0] = dp[i-1][0] + dp[i-1][1];
				dp[i][1] = dp[i-1][0];
			}
			
			System.out.println("#" + t + " " + dp[k-1][0] + " " + dp[k-1][1]);
		}
	}
}