[SWEA] JAVA / D2 - +=

SWEA - +=

문제 분석

프로그래밍 언어에는 += 연산자가 있다
x += y = x = x + y 이런식으로 x의 값이 바뀐다
문제에서는 x에 저장된 값은 A, y에 저장된 값은 B라고 한다
x += y, y += x의 연산을 원하는 만큼 수행해서 x 와 y 둘 중 하나 이상의 저장된 값이 N이 초과가 되게 하려고 할 때, 최소 몇 번 수행해야 하는지 계산하는 프로그램을 만드는 것이 목적

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다
각 줄에는 세 개의 정수가 주어짐

테스트 케이스 개수는 60만개 이상으로 상당히 많다

출력

문제와 같이 x 와 y 둘 중 하나 이상의 저장된 값이 N초과가 되게 하려고 할 때, 최소 몇 번 수행해야 하는지 계산하는 프로그램을 만드는 것이 목적

코드 구현

import java.util.*;
import java.io.*;

public class No_21425 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());

		for(int i = 0; i < T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int N = Integer.parseInt(st.nextToken());
			
			int count = 0;
			
			while (A <= N && B <= N) {
				if(A < B) {
					A += B;
				} else {
					B += A;
				}
				count++;
			}
			System.out.println(count);
		}
	}
}

---

💡 문제 풀이

A 또는 B 둘 중 하나라도 N을 초과하게 만들면 되기 때문에 값을 빨리 키우는 게 좋다
항상 더 작은 값을 더 큰 값에 더해주는 로직을 만들면 된다 예시를 들어보자
만약 A=2, B=5, N=10 일 때

• if(A < B)

  • A += B 실행 -> A = A + B
    • 2 + 5 = 7 (N을 초과하지 않음) 1회
    • 7 + 5 = 12 (N을 초과) 2회 // 총 2회
  • B += A 실행 -> B = B + A
    • 5 + 2 = 7 (N을 초과하지 않음) 1회
    • 7 + 2 = 9 (N을 초과하지 않음) 2회
    • 9 + 2 = 11 (N을 초과) 3회 // 총 3회

따라서 더 작은 값을 큰 값에 더해주면 된다!

💡이것을 탐욕 알고리즘(Greedy Algorithm) 이라고 부른다
매 순간 가장 좋아 보이는 선택을 하는 것 기억해두자