[C++] 프로그래머스 : 퍼즐 게임 챌린지

문제

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

프로그래머스

 

풀이

이진 탐색으로 가능한 숙련도의 최솟값을 찾아간다.

이진 탐색이 아닌, 예를 들어 증감연산자를 통해 모든 가능한 숙련도를 비교하려 할 경우 시간초과가 발생한다.

 

1. answer의 초기값은 diffs의 최댓값의 절반으로 설정한다. 그리고 cur_level(=퍼즐 맞춰지는지 실험해볼 숙련도)의 초기값은 answer로 설정한다.

 

2. while문 안에서 최소 숙련도를 찾아 answer에 저장하는 작업을 수행할 것이다. 이때 나는 이진 탐색을 사용하여 만약 현재 cur_level로 퍼즐을 완료가 가능한 경우 더 작은 숙련도에 대해 퍼즐을 맞출 수 있는지를 확인할 것이고, 만약 cur_level로 퍼즐을 완료할 수 없는 경우 더 큰 cur_level로 퍼즐을 맞출 수 있는지를 확인할 것이다.

 

주의해야 할 점은, 문제에서 숙련도(=answer)는 항상 양의 정수만 가능하다고 했으므로 만약 0이하의 정수가 나온 경우에 대해서 항상 1을 반환해주는 코드를 추가해주었다.

(= test14의 내용이다. 반환되는 값은 항상 1 이상의 정수여야 한다.)

 

자세한 구현 방법은 아래 코드의 주석에서 확인할 수 있다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

    int max = *max_element(diffs.begin(), diffs.end());

    // answer의 초기값은 중간값
    answer = (max + diffs[0])/2;
    int arr_size = (max + diffs[0]) / 2;

    long long min_time = 0;
    
    int cur_level = answer;
    
    while(true){
        // 탐색 종료 시점 
        if(arr_size == 0) break;
        
        // answer로 문제 푸는 데 걸리는 시간 초기값
        long long cur_time = 0;
        
        cur_time += times[0];
        for(int i=1; i<diffs.size(); i++){
            int a = 0;
            if(diffs[i] > cur_level) a = diffs[i] - cur_level;
            cur_time += a * (times[i] + times[i-1]) + times[i];
        }

        // 현재 level 로 문제를 풀 수 있는 경우 
        if(cur_time <= limit){
            answer = cur_level;
            cur_level-=arr_size;
            arr_size /=2;
        }
        
        // 현재 level 로 문제를 풀 수 없는 경우 
        else{
            // answer 업데이트 없이 cur-level 만 update
            cur_level += arr_size;
        } 
    }
    
    if(answer <=0) answer = 1;
    return answer;
}

 

 

메모

이진 탐색 종료 시점을 처음에 떠올리기 쉽지 않았다. 

난 항상 answer에 자연수만 반환된다고 생각했는데, 그렇지 않는 경우가 존재했다. 그래서 test14를 계속 통과하지 못했는데, 이를 해결하기 위한 조건문을 추가해 해결할 수 있었다.