[SWEA]21425. +=

문제링크

 

 

처음에는 이거 어떻게 푸는 문제여? 싶었지만 그리디 알고리즘이라는 걸 파악했다.

문제를 요약하자면

• 현재 값이 (x, y)이고
• 두 값 중 하나라도 N을 초과할 때까지
• "x += y" 또는 "y += x" 연산을 원하는 대로
• 연산 횟수를 최소로 만들고 싶다.

그런데 이때 매번 둘 중 더 작은 값에 더 큰 값을 더하는 게 최적이라는 걸 알 수 있다.

• 예를 들어, x가 작고 y가 크다면, x에 y를 더하는 x += y를 하면 x가 크게 증가하니까 빠르게 N을 넘을 수 있다.
• 반대로, y가 작고 x가 크다면, y += x를 해서 y를 크게 키워야 한다.

---

풀이

 

import java.util.Scanner;

public class JAVA1 {

    static Scanner sc = new Scanner(System.in);

    public static void solution(int n){

        int [] answer = new int[3];

        for(int i=0;i<n;i++){
            int count=0;
            for(int j=0;j<3;j++){
                answer[j] = sc.nextInt();
            }
            while(answer[0] <= answer[2] && answer[1] <= answer[2]){
                if(answer[0]<answer[1]){
                    answer[0] += answer[1];
                    count++;
                }
                else{
                    answer[1] += answer[0];
                    count++;
                }
            }
            System.out.println(count);
        }
    }

    public static void main(String[] args) {
        int n = sc.nextInt();
        solution(n);
    }
}