[코테 - Java] SWEA 문제 21425번 +=

1. 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

 

2. 내가 푼 답안

import java.util.*;

public class Main {
    public int solutions(int a, int b, int n) {
        int answer = 0;

        while (a <= n && b <= n) {
            if (a < b) {
                a += b;
            } else {
                b += a;
            }
            answer++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0 ; i < num ; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int n = scanner.nextInt();

            System.out.println(T.solutions(a, b, n));
        }
    }
}

3. 정리

이 문제를 풀면서 메모리에 대해서 공부했다.

처음에는 bfs를 이용해서 풀었는데, 계속 런타임 에러가 났다. 그 이유를 살펴보니 내가 메모리 설계에 실패한 것이었다..!

그래서 그리디로 풀어서 제출했더니 pass가 떴다.

 

<메모리 정리>

int = 4 bytes

1MB = 1,048,576 bytes

 

위 문제에서는 n이 최대 10^9이므로,

최대 int 당, (4 * 1,000,000,000) bytes / 1,048,576 = 약 3,814.7MB

이다. 따라서 bfs로 풀면 visited에 쌓이기 때문에 메모리는 초과이다.

 

따라서 그리디로 풀어줘야한다.