99클럽 코테 스터디 13일차 TIL

백준 - 27961번

풀이

생성 마법은 고양이를 1마리씩 소환하고, 복제 마법은 현재 고양이 수 이하만큼 소환할 수 있다. 

생성 마법이든 복제 마법이든 최소한의 행동으로 입력된 n마리의 고양이를 소환해야 한다. 

두 가지 마법 중 가장 최적의 마법을 선택하고, 현재 고양이 수에서 해당 마법으로 추가한 고양이 수를 더한다.

이 과정을 고양이 수가 n이 될 때까지 반복한다. 이때, 마법이 선택될 때마다 행동 횟수를 증가시킨다.

 

구현1 - 실패(시간초과)

import java.util.Scanner;

public class Main {

    static long catCount = 0; // 현재 고양이 수
    static final int GENERATE_COUNT = 1; // 생성 마법은 무조건 1마리씩 추가한다.

    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        int action = 0; // 행동 횟수

        while (catCount < n) {
            long remainingCount = n - catCount; // 추가해야 할 고양이 수

            long generate = catCount + GENERATE_COUNT;
            long copyCount = copy(remainingCount);
            long copy = catCount + copyCount;

            long max = generate >= copy ? GENERATE_COUNT : copyCount;

            catCount += max;
            action++;
        }

        System.out.println(action);
        sc.close();
    }

    static long copy(long remainingCount) {
        long result = 0;
        for (long i = 0; i <= catCount; i++) {
            if (i <= remainingCount) {
                result = Math.max(result, i);
            }
        }
        return result;
    }
}

추가되는 고양이 수를 구하는 마법 중, copy 메서드의 catCount 순회가 시간초과의 원인이었다.

예제 입력 3번처럼 2147483648 값이 들어온다면 catCount의 값이 커질때마다 그만큼 순회해야 한다. 

 

copy 메서드를 살펴보면, catCount를 순회하면서 remainingCount의 작은 값들 중 최댓값을 찾아 반환하고 있다.

결국, 현재 고양이 수(catCount)가 추가해야할 고양이 수(remainingCount)보다 작다면 현재 고양이 수를 반환하고,

반대라면 추가해야할 고양이 수를 반환하면 된다.

int copyCount = Math.min(catCount, remainingCount);

구현2

import java.util.Scanner;

public class Main {

    static long catCount = 0;
    static final int GENERATE_COUNT = 1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        int action = 0;

        while (catCount < n) {
            long remainingCount = n - catCount;
            
            long generate = catCount + GENERATE_COUNT;
            long copyCount = Math.min(catCount, remainingCount);
            long copy = catCount + copyCount;
            
            long max = generate >= copy ? GENERATE_COUNT : copyCount;

            catCount += max;
            action++;
        }

        System.out.println(action);
        sc.close();
    }
}

---

여러 방법 중 가장 최적이라고 생각되는 방법을 선택하여 해결하는 Greedy 알고리즘 문제였다.

 

각 방법들에 대한 최적해을 구하고, 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.

생성 마법(A), 복제 마법(B)을 사용하여 추가할 고양이 수 계산.
A, B 를 현재 고양이 수에 각각 더했을 때, n에 가장 근접한 값을 선택.
선택한 마법으로 고양이를 추가했고, 마법을 사용할 때마다 행동 횟수를 증가시킴.

 

복잡한 계산이 필요하지 않아 시간복잡도가 낮다는 장점이 있지만, 

모든 문제에서 최적해를 보장하지 않고, Greedy의 선택이 항상 최적해로 이어지지 않을 수 있다는 단점도 있다.

---

백준 27961번 고양이는 많을수록 좋다.

https://www.acmicpc.net/problem/27961