SW Expert Academy_GCD

//알고리즘

1. DP

2. 규칙을 찾아내고 DP 테이블을 만들어 계산

 

풀이 1.

import java.util.Scanner;

public class GCD2 {
	static int T, K, cnt, A, B;
	static long[] v;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		v = new long[93];
		for (int tc = 1; tc <= T; tc++) {
			K = sc.nextInt();
			v[0] = 0;
			v[1] = 1;

			for (int i = 2; i < v.length; i++) {
				v[i] = v[i - 1] + v[i - 2];
			}

			System.out.printf("#%d %d %d\n", tc, v[K + 2], v[K + 1]);
		}
	}

}

 

풀이 2.

import java.util.Scanner;

public class GCD {
	static int T, K, cnt, A, B;
	static long[][] v;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		v = new long[91][2];

		// 알고리즘
		// 피보나치 수열
		for (int tc = 1; tc <= T; tc++) {
			K = sc.nextInt();
			int a = 2;
			int b = 1;
			v[1][0] = 2;
			v[1][1] = 1;
			v[2][0] = 3;
			v[2][1] = 2;

			for (int i = 3; i <= K; i++) {
				v[i][0] = v[i - 1][0] + v[i - 2][0];
				v[i][1] = v[i - 1][1] + v[i - 2][1];
			}

			System.out.printf("#%d %d %d\n", tc, v[K][0], v[K][1]);
		}
	}

}