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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/340212

프로그래머스

정답 코드

#include <string>
#include <vector>

using namespace std;

// 레벨과 난이도를 넣으면 소요 시간을 계산
long long calcTime(int lv, int diff, int prev_time, int work_time){
    long long t = work_time;
    if (diff > lv)
        t += (diff - lv) * (prev_time + work_time);
    return t;
}

// 레벨을 넣으면 전체 소요시간을 반환
long long calcAll(int lv, vector<int> &diffs, vector<int>& times){
    long long sum = 0;
    for(int i=0; i < diffs.size(); i++){
        if (i == 0)
            sum += calcTime(lv,diffs[i],0,times[i]);
        else
            sum += calcTime(lv,diffs[i], times[i-1],times[i]);
    }
    return sum;
}

// 모든 배열 순회하면서 레벨 넣는 연산 (복잡도 100000 * 1000)
int binSearch(int min_lv, int max_lv, 
              vector<int> &diffs, vector<int>& times, long long limit){
    int mid_lv = (min_lv + max_lv) / 2;
    long long sum = calcAll(mid_lv, diffs, times);
    if (sum == limit)
        return mid_lv;
    if (max_lv - min_lv <= 1){
        if (calcAll(min_lv, diffs, times) <= limit)
            return min_lv;
        return max_lv; 
    }
    if (sum < limit)
        return binSearch(min_lv, mid_lv, diffs,times,limit);
    else
        return binSearch(mid_lv + 1,max_lv,diffs,times,limit);
}

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = binSearch(1,1000000,diffs,times,limit);
    return answer;
}

 

문제 풀이의 흐름

1. 가능한 퍼즐의 난이도를 구하는 문제구나 일단 먼저 수식을 세우자.

2. 수식을 calcTime에 세우고 calcAll에서 해당 레벨에서 얻을 수 있는 점수를 다 구했다.

3. 최대 레벨에서 1씩 줄이면서 불가능해지는 시점이 정답이다.

4. 그렇다면 이렇게 풀면 시간 복잡도상 문제를 풀 수 있는가?

5. 간단한 시간 복잡도 계산 -> 난이도 최대값 * time 배열의 길이 n -> 100,000 * 300,000 -> 30,000,000,000 대충 계산해도 너무 큰 시간이 걸린다.

6. 여기서 이분탐색을 떠올렸는데 time 배열의 길이 n * log 난이도 최대값 -> 300,000 * log(100,000) -> 300,000* 1000(이하) 따라서 가능하다는 판단을 하고 이분탐색 풀이를 생각했다.

 

 

주의 할 점

특히 헷갈렸던 부분은 아래 부분이다.

if (sum == limit)
        return mid_lv;
    if (max_lv - min_lv <= 1){
        if (calcAll(min_lv, diffs, times) <= limit)
            return min_lv;
        return max_lv; 
    }
  if (sum < limit)
        return binSearch(min_lv, mid_lv, diffs,times,limit);
    else
        return binSearch(mid_lv + 1,max_lv,diffs,times,limit);

이 부분의 경우 종료조건이 헷갈려서 직접 넣어보면서 문제를 풀었다.

사실 이런 부분이 빠르게 생각나려면 직접 사례를 생각하는게 아니라 이론적으로 계산하고 그 결과에 대한 암기가 필수 인것 같은데 오랜만에 이분탐색이라 잘 안됐다.

반성 및 고찰

더 간단한 풀이가 여기에 있다.

코테를 안 푼지가 오래돼서 이렇게 간단하게 풀 수 있는데, 생각이 안 났다..

그래도 처음부터 이분탐색은 생각해서 다행이다.

다음부터는 더 생각을 해서 풀어보자.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

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

    int high = 100000;
    int low = 1;
    int mid;
    long long int totalTime;

    while(high >= low)
    {
        mid = (high + low) / 2;
        totalTime = 0;
        for(int i = 0; i < diffs.size(); i++)
        {
            totalTime += times[i];
            if(mid < diffs[i])
            {
                totalTime += (times[i-1] + times[i]) * (diffs[i] - mid);
            }

            if(totalTime > limit)
            {
                break;
            }
        }

        if(totalTime > limit)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }

    answer = low;

    return answer;
}