[SWEA]D4 8659 GCD

SWEA D4 8659 GCD

 

 

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW1l1s2KWn4DFARC

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/HsiWrWxymRM

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d4;

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

/**
 * (k = 0) GCD(1, 0) = 1 --> b가 0이면 1이다. a는 그때 b보다 큰 가장 작은 수
 * (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 = 4) GCD(8, 5) = GCD(5, 8 % 5) = GCD(5, 3) = GCD(3, 2) = GCD(2, 1) = GCD(1, 0) = 1
 * 
 * a[k] = a[k-1] + b[k-1]
 * b[k] = a[k-1]
 * 점화식을 찾아보면
 * 
 * @author 은서파
 * @since 2022. 2. 12.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW1l1s2KWn4DFARC
 * @git https://github.com/quietjun/algo_aps/blob/master/src/se/code/d4/SWEA_D4_8659_GCD.java
 * @youtube
 * @performance 23,004 kb, 107 ms
 * @category #DP
 * @note
 */
public class SWEA_D4_8659_GCD {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();

    private static int T, K;
    // k를 index로 해서 요구사항을 만족하는 a와 b 즉 memo[k] = [a][b]
    private static long[][] memo;

    public static void main(String[] args) throws IOException {
        // 한번 구해놓고 전체 테케에서 재활용
        setup();
        input = new BufferedReader(new StringReader(src));
        T = Integer.parseInt(input.readLine());
        for (int t = 1; t <= T; t++) {
            K = Integer.parseInt(input.readLine());
            output.append(String.format("#%d %d %d%n", t, memo[K][0], memo[K][1]));
        }
        System.out.println(output);
    }

    private static void setup() {
        memo = new long[91][2];
        memo[0] = new long[] { 1, 0 };
        memo[1] = new long[] { 2, 1 };

        for (int k = 2; k < 91; k++) {
            memo[k][0] = memo[k - 1][0] + memo[k - 1][1];
            memo[k][1] = memo[k - 1][0];
        }
    }

    // REMOVE_START
    private static String src = "3\r\n" +
                                "1\r\n" +
                                "3\r\n" +
                                "20";
    // REMOVE_END
}