SWEA(SW Expert Academy) 21425. += D2

● 문제출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZD8K_UayDoDFAVs&categoryId=AZD8K_UayDoDFAVs&categoryType=CODE&problemTitle=21425&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

●정리(요약)

정수형 변수 x, y가 있을 때 “x += y”를 하면 x에 저장된 값이 (기존에 x에 저장되어 있던 값) + (기존에 y에 저장되어 있던 값)으로 바뀐다.

현재 x에 저장된 값은 A, y에 저장된 값은 B이다. 당신은 “x += y” 또는 “y += x” 연산을 원하는 순서대로 원하는 만큼 수행하여, x나 y 둘 중 하나 이상에 저장된 값이 N 초과가 되게 하려고 한다. 연산을 합쳐서 최소 몇 번 수행해야 하는지 계산하는 프로그램을 작성하라.

<입력>
테스트 케이스 수 T
A,B,N

<출력>
N을 초과하려면 최소 몇 번 수행하는지 계산

●코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Solution
{
 
    static int A , B, N;
    static int cnt;
 
    public static void main(String args[])  throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
         
        for(int i = 0 ; i < T; i++) {
            st= new StringTokenizer(br.readLine()," ");
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            cnt=0;
             
            if(A>B) {
                dfs(A,B);   
            }else {
                dfs(B,A);
            }
             
            sb.append(cnt).append("\n");
             
        }
        System.out.println(sb);
    }
     
     
    public static void dfs (int x , int y) {
        int sum = x+y;
        cnt++;
        if(sum>N) {
            return;
        }
        dfs(sum,x);
    }
 
}

●느낀 점

이해하는데 한 참 걸렸다...
마지막을 예를 들어 보자면
10+7 - 17+10 - 27+17 - 44+27 - 71+44 - 115+71 - 186+115 - 301+186 - 487+301 - 788+487 - 1275
따라서 11번 수행해야한다.
그래서 dfs(큰값, 작은값) 재귀함수 을 사용하여 sum>N이 되면 cnt가 몇 개 인지 계산하도록 코드를 작성하였다.