[Programmers] Lv.2 - 퍼즐 게임 챌린지

🍥 문제

[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

---

🍥 접근

• diffs, times의 길이가 3 x 10⁴ 으로 제한.
  • O(NlogN), O(N), O(logN)의 시간 복잡도를 가지는 알고리즘을 이용해야 함을 알 수 있음.
• 어떤 조건에 의한 ~ 최솟값, 최댓값 이런 문구?
  • 일단은 이진 탐색을 의심해 보자.

이진 탐색의 first, last 구하기

개요

이진 탐색에서 구해야 할 answer의 값을 보통 first, last, mid로 도출되도록 짠다.

first?

내가 가질 수 있는 숙련도(level)의 최소는 제한 사항에서 1이라고 명시됨.

last?

제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.

위의 문구에서 도출할 수 있는 것은 입력 = 난이도(diffs)는 제한 시간에 무조건 골인.

따라서, diffs의 가장 큰 max 값이 입력이란 상황에서 가질 수 있는 가장 큰 난이도라는 것을 알 수 있음.

무얼 기준으로 탐색하는데요?

탐색을 끝내야 할 시점은 결국 주어진 난이도를 토대로 퍼즐 문제들을 푼 시간이 총 얼마나 걸리냐가 핵심이다. 퍼즐을 푼 시간이 주어진 Limit 시간 전에는 풀어야 되는 것이다.

---

🍥 슈도 코드

잘 안 풀리는 말, 자꾸 헷갈려서 앞에 보고 뒤에 보고 왔다 갔다 해야 될 땐 무조건 한글로 옮기는 게 최고다. 그냥 무조건 최고다. 슈도 코드를 쓸 줄 알면 코딩은 자연스레 된다. 일단 해 보자.

문제 풀이 시간 구하기

if (퍼즐 난이도가 적당하거나 쉽다면)
{
    해당 문제는 (현재 문제 풀이 시간)에 풂.
}
else // 퍼즐 난이도가 어렵다면
{
    틀린 횟수 = 문제를 (난이도 - 레벨) 만큼 틀림.
    틀릴 때마다 (현재 문제 푸는 시간) + (이전 문제 풀이 시간)이 걸림.
    다 틀리고 나면 (현재 문제 풀이 시간) 만큼 걸림.
    
    따라서,
    ((현재 문제 푸는 시간) + (이전 문제 풀이 시간)) * (틀린 횟수) + (현재 문제 풀이 시간)
    만에 문제를 풂.
}

탐색 범위 조정

해당 숙련도에 따른 총 문제 풀이 시간을 구하고 난 후에는 이게 제한 시간 안에 들어 있는지, 아닌지 확인했다. 그 뒤엔 어떻게 해야 되는가?

어렵고, 헷갈리고, 당최 무슨 말인지 모를 땐 케이스를 적용해서 생각한다.

문제에서 제공한 입출력 예 #1을 활용하자. (제한 시간이 30 가정)

제한 시간 = 30

if (문제 푼 시간이 30분보다 덜 걸린다면)
{
    문제가 쉽다는 뜻이다.
    나의 숙련도(level)을 낮춰도 될 것 같다.
    탐색 범위를 mid의 왼쪽으로 한다.
}
else
{
    문제가 어렵다는 뜻이다.
    나의 숙련도(level)을 올려야 할 것 같다. 
    탐색 범위를 mid의 오른쪽으로 한다.
}       

---

🍥 코드

int solution(vector<int> diffs, vector<int> times, long long limit)
{
    int answer = 0;

    vector<int> diffs_copy(diffs);
    sort(diffs_copy.begin(), diffs_copy.end());

    long long first = 1;
    long long last = diffs_copy.back();

    while (first <= last)
    {
        long long mid = (first + last) / 2;
        long long time = 0;

        for (int i = 0; i < diffs.size(); ++i)
        {
            if (mid >= diffs[i])
            {
                time += times[i];
            }
            else
            {
                long long how_much_X = diffs[i] - mid;
                long long how_long_time = (times[i] + times[i - 1]) * how_much_X + times[i];
                time += how_long_time;
            }
        }

        if (time <= limit)
        {
            last = mid - 1;
            answer = mid;
        }
        else
        {
            first = mid + 1;
        }
    }

    return answer;
}