퍼즐 게임 챌린지

문제 설명

당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다.
각 퍼즐은 난이도와 소요 시간이 정해져 있습니다.
당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다.
현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면,
게임은 다음과 같이 진행됩니다.

1. diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
2. diff > level이면, 퍼즐을 총 diff - level번 틀립니다.
   퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며,
   추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다.
   이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다.
   diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.

퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다.
제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다.
(난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.)
퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs,
퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times,
전체 제한 시간 limit이 매개변수로 주어집니다.
제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

풀이

public class PuzzleGameSolver
{
    static int[] _diffs;
    static int[] _times;
    static long _limit;
    static int _puzzleCount;

    public static int Solution(int[] diffs, int[] times, long limit)
    {
        _diffs = diffs;
        _times = times;
        _limit = limit;
        _puzzleCount = diffs.Length;

        const int maxvalue = 100000;
        
        int highLevel = maxvalue;
        int lowLevel = 0;
        int resultLevel = 0;

        while (lowLevel <= highLevel)
        {
            //가장 큰 숫자와 가장 작은 숫자의 평균을 레벨로 입력
            int level = lowLevel + (highLevel - lowLevel) / 2;
            
            bool isInLimit = Check(level);

            if (isInLimit)
            {
                resultLevel = level;
                highLevel = level - 1;
            }
            else
            {
                lowLevel = level + 1;
            }
        }

        return resultLevel;
    }
    
    private static bool Check(int level)
    {
        long totalTime = 0;
        long prevTime = 0; // SolvePuzzle 함수에서 필요

        for (int i = 0; i < _puzzleCount; i++)
        {
            totalTime += SolvePuzzle(level, _diffs[i], _times[i], prevTime);
            // 총 시간이 limit을 초과하면 더 이상 계산할 필요 없음 (성능 최적화)
            if (totalTime > _limit) 
            {
                return false;
            }
            prevTime = _times[i];
        }
        return totalTime <= _limit;
    }

    private static long SolvePuzzle(int level, int diff, int time, long prevTime)
    {
        if (diff <= level)
        {
            return time;
        }

        long solveTime = (diff - level) * (prevTime + time) + time;
        
        return solveTime;
    }
}

• 문제 설명부터 너무 길어 이해하는게 쉽지 않았지만 천천히 과정을 뜯어보면서 풀어보았음
• 클래스 내 여러 함수에서 사용하는 요소에 대해서 전역 변수로 선언하였음

    static int[] _diffs;
    static int[] _times;
    static long _limit;
    static int _puzzleCount;
    
    
    public static int Solution(int[] diffs, int[] times, long limit)
    {
        _diffs = diffs;
        _times = times;
        _limit = limit;
        _puzzleCount = diffs.Length;
        
        ...

• 이후 Solution 함수에서 바로 해당 요소들을 입력해줌

문제 풀이 함수

    private static long SolvePuzzle(int level, int diff, int time, long prevTime)
    {
        if (diff <= level)
        {
            return time;
        }

        long solveTime = (diff - level) * (prevTime + time) + time;
        
        return solveTime;
    }

• 제시된 규칙에 따라 문제를 푸는 함수
• 숙련도를 의미하는 level에 따라 구분해서 계산을 실행
• 각각의 문제에 대해서 소요되는 시간을 계산하고 이를 반환하는데 이를 전부 더해 전체 소요 시간을 계산

제한 시간 검사 함수

    private static bool Check(int level)
    {
        long totalTime = 0;
        long prevTime = 0; // SolvePuzzle 함수에서 필요

        for (int i = 0; i < _puzzleCount; i++)
        {
            totalTime += SolvePuzzle(level, _diffs[i], _times[i], prevTime);
            // 총 시간이 limit을 초과하면 더 이상 계산할 필요 없음 (성능 최적화)
            if (totalTime > _limit) 
            {
                return false;
            }
            prevTime = _times[i];
        }
        return totalTime <= _limit;
    }

• 위 함수를 통해 각각의 문제에 대해서 반복문을 통해 검사를 실시하고 제한 시간 내에 풀었는지를 확인하여 반환

최소 숙련도 찾기

• 검색 횟수를 최적화 하기 위해 2진 검색수를 최적화 하기 위해 이진 탐색 방법을 사용함
• 제시된 최대 숙련도를 const int maxvalue = 100000 선언해주고 해당 값과 최저 숙련도인 0 값의 평균을 통해 검사를 실시

        int highLevel = maxvalue;
        int lowLevel = 0;
        int resultLevel = 0;

        while (lowLevel <= highLevel)
        {
            //가장 큰 숫자와 가장 작은 숫자의 평균을 레벨로 입력
            int level = lowLevel + (highLevel - lowLevel) / 2;
            
            bool isInLimit = Check(level);

            if (isInLimit)
            {
                resultLevel = level;
                highLevel = level - 1;
            }
            else
            {
                lowLevel = level + 1;
            }
        }

• 만약 제한 시간 내에 문제를 풀 수 있었다면 우리가 찾고자 하는 최소 숙련도는 평균보다 작은 절반의 영역에 있는 것이므로 최대 숙련도 값을 이번에 사용한 level보다 1 작은 값을 입력하여 검색하도록 함
• 만약 제한 시간 내에 풀지 못했다면 우리가 찾고자 하는 최소 숙련도가 큰 절반 영역에 있는 것이므로 최소 숙련도 수치를 갱신
• 이렇게 해서 최소 값과 최대 값이 같아질 때 찾고자 하는 숙련도 값을 알 수 있음