[SWEA]#8659 GCD

SeungBird·2020년 8월 26일
0

⌨알고리즘(SWEA)

목록 보기
6/31

문제

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

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

돈 보다 문제 내는 것을 더 좋아하는 이상한 동욱이는 피자를 사러 온 의석이에게 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의 정답을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 정해진 % 연산자의 수행 회수 K(1≤K≤90)이 주어진다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스마다 원하는 조합을 만족하는 두 개의 수 A, B (A>B)를 공백으로 출력한다.

예제 입력 1

3     // 테스트 케이스 개수
1     // 첫 번째 테스트 케이스 K = 1
3
20	

예제 출력 1

#1 2 1    // 첫 번째 테스트 케이스 결과
#2 5 3
#3 17711 10946

풀이

import java.util.Scanner;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
         
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            long a=1;
            long b=1;
            long k=0;
             
            for(int i=0; i<N; i++) {
                k=a;
                a=a+b;
                b=k;
            }
            
            System.out.println("#"+test_case+" "+a+" "+b);
        }
    }
}
profile
👶🏻Jr. Programmer

0개의 댓글