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

문제 설명

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

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

예를 들어 diff=3, time_cur=2, time_prev=4인 경우, level에 따라 퍼즐을 푸는데 걸리는 시간은 다음과 같습니다.

• level=1이면, 퍼즐을 3-1=2번 틀립니다. 한 번 틀릴 때마다 2+4=6의 시간을 사용하고, 다시 퍼즐을 푸는 데 2의 시간을 사용하므로 총 6x2+2=14의 시간을 사용하게 됩니다.
• level=2이면, 퍼즐을 3-2=1번 틀리므로, 6+2=8의 시간을 사용하게 됩니다.
• level>=3이면 퍼즐을 틀리지 않으며, 2의 시간을 사용하게 됩니다.

퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.

 

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return하도록 solution 하수를 완성해 주세요.

 

 

제한사항

• 1<=diffs의 길이=times의 길이=n<=300,000
  • diffs[i]는 i번째 퍼즐의 난이도, times[i]는 i번째 퍼즐의 소요 시간입니다.
  • diffs[0]=1
  • 1<=diffs[i]<=100,000
  • 1<=times[i]<=10,000
• 1<=limit<=10^15
  • 제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.

 

 

입출력 예

diffs			times	limit	result	설명
[1, 5, 3]			[2, 4, 7]	30	3	숙련도가 3인 경우 다음과 같이 진행됩니다. - 1번째 퍼즐을 2의 시간을 사용하여 해결합니다. - 2번째 퍼즐을 5-3=2번 틀려서 총(4+2)x2+4=16의 시간을 사용하여 해결합니다. - 3번째 퍼즐을 7의 시간을 사용하여 해결합니다. 총 2+16+7=25의 시간을 사용하여 모든 퍼즐을 해결할 수 있습니다. 숙련도가 3보다 작은 경우 제한 시간인 30 이내에 모든 퍼즐을 해결할 수 없습니다. 따라서 3을 return해야 합니다.
[1, 4, 4, 2]			[6, 3, 8, 2]	59	2	숙련도가 2인 경우 다음과 같이 진행됩니다. - 1번째 퍼즐을 6의 시간을 사용하여 해결합니다. - 2번째 퍼즐을 4-2=2번 틀려서 총(3+6)*2+3=21의 시간을 사용하여 해결합니다. - 3번째 퍼즐을 4-2=2번 틀려서 총(8+3)*2+8=30의 시간을 사용하여 해결합니다. - 4번째 퍼즐을 2의 시간을 사용하여 해결합니다. 총 6+21+30+2=59의 시간을 사용하여 모든 퍼즐을 해결할 수 있ㅅ브니다. 숙련도가 2보다 작은 경우 제한 시간인 59 이내에 모든 퍼즐을 해결할 수 없습니다. 따라서 2를 return해야 합니다.
[1, 328, 467, 209, 54]			[2, 7, 1, 4, 3]	1723	294	숙련도가 294인 경우 다음과 같이 진행됩니다. - 1번째 퍼즐을 2의 시간을 사용하여 해결합니다. - 2번째 퍼즐을 328 - 294 = 34번 틀려서 총 (7 + 2) × 34 + 7 = 313의 시간을 사용하여 해결합니다. - 3번째 퍼즐을 467 - 294 = 173번 틀려서 총 (1 + 7) × 173 + 1 = 1385의 시간을 사용하여 해결합니다. - 4번째 퍼즐을 4의 시간을 사용하여 해결합니다. - 5번째 퍼즐을 3의 시간을 사용하여 해결합니다. 총 2 + 313 + 1385 + 4 + 3 = 1707의 시간을 사용하여 모든 퍼즐을 해결할 수 있습니다. 숙련도가 294보다 작은 경우 제한 시간인 1723 이내에 모든 퍼즐을 해결할 수 없습니다. 따라서 294를 return 해야 합니다.
[1, 99999, 100000, 99995]			[999, 9001, 9999, 9001]	3456789012	39354	숙련도가 39354인 경우 다음과 같이 진행됩니다. - 1번째 퍼즐을 9999의 시간을 사용하여 해결합니다. - 2번째 퍼즐을 99999 - 39354 = 60645번 틀려서 총 (9001 + 9999) × 60645 + 9001 = 1152264001의 시간을 사용하여 해결합니다. - 3번째 퍼즐을 100000 - 39354 = 60646번 틀려서 총 (9999 + 9001) × 60646 + 9999 = 1152283999의 시간을 사용하여 해결합니다. - 4번째 퍼즐을 99995 - 39354 = 60641번 틀려서 총 (9001 + 9999) × 60641 + 9001 = 1152188001의 시간을 사용하여 해결합니다. 총 9999 + 1152264001 + 1152283999 + 1152188001 = 3456746000의 시간을 사용하여 모든 퍼즐을 해결할 수 있습니다. 숙련도가 39354보다 작은 경우 제한 시간인 3456789012 이내에 모든 퍼즐을 해결할 수 없습니다. 따라서 39354를 return 해야 합니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0; // 리턴 값
    int level=1; // 플레이어 숙련도
    long long used_time; // 최종 소요 시간
    int max_diffs=*(max_element(diffs.begin(), diffs.end()));
    int min_diffs=1;
    
    // 제한 시간 내 퍼즐을 해결할 때까지 반복
    do 
    {
        used_time=0; // 소요 시간 초기화
        level=(min_diffs+max_diffs)/2;
        
        // 얼마나 걸리는지 used_time 계산
        for(int i=0; i<diffs.size(); i++)
        {
            // 난이도(diff)가 level에 맞음
            if(level>=diffs[i])
            {
                used_time+=times[i];
            }
            else // 난이도가(diffs)가 level에 안맞음
            {
                // diffs[i]-level 만큼 틀림
                // 한번 틀릴 때마다, times[i] 만큼의 시간을 사용
                // 추가로 time[i-1]만큼의 시간을 사용해 이전 퍼즐을 다시 풀고와야 함
                // diffs[i]-level번 틀린 이후 다시 퍼즐을 풀면 times[i] 만큼의 시간을 사용
                used_time+=((diffs[i]-level)*(times[i]+times[i-1]))+times[i];
            }
        }
        
        // level로 limit안에 풀 수 있을 때
        if(used_time<=limit)
        {
            // level을 저장하고 더 낮춰봄
            answer=level;
            max_diffs=level-1;
        }
        else // level로 limit 안에 풀 수 없을 때
        {
            // level을 높여야 함
            min_diffs=level+1;
        }
    }
    while(min_diffs<=max_diffs);
    
    answer=min_diffs;
    return answer;
}

 

정말 짧게 이야기하면 n개의 퍼즐을 푸는데 걸리는 시간이 limit를 넘지 않는 숙련도의 최소값을 구하는 것이다. 이제 퍼즐 푸는데 걸리는 시간을 좀 길게 설명해 놓은 것이다. 숙련도(level)가 문제의 난이도(diffs[i])보다 크거나 같으면 나한테 이 문제는 쉬운 문제이기 때문에 문제 풀리는데 걸리는 시간(times[i]) 그대로 걸린다. 하지만 만약 내 숙련도가 문제의 난이도 보다 못하다면 원래 문제 푸는데 걸리는 시간보다 더 걸릴 것이다. 여기선 더 걸리는 시간을 이렇게 설정하였다.

(문제의 난이도-내 숙련도)*(지금 문제 푸는데 걸리는 시간+바로 전 문제에서 걸리는 시간)+지금 문제 푸는데 걸리는 시간

 

자 그럼 n개의 퍼즐을 푸는데 걸리는 시간을 계산하는 방법은 어느정도 윤곽이 보이기 시작한다. for문을 이용해 문제의 갯수만큼 돌면서 각문제들의 난이도와 내 숙련도를 비교하여 걸리는 시간들을 더해 나가면 되는 것이다. 나는 이 걸리는 시간을 used_time이라는 변수로 만들었다.limit가 long long 이길래 이것도 long long으로 해주었다.for문 안에서 if문을 이용해 level>=diffs[i]를 확인하여 참이라면 그냥 현재 문제를 푸는데 걸리는 시간을 더하고 거짓이라면 위에 저 박스에 들어있는 식에 띠라 시간을 계산해 더해주었다. 

 

여기까지가 내가 특정 level일 때 총 몇시간이 걸리는지 알아볼 수 있는 코드다. 이제 문제 푸는데 걸리는 시간이 limit를 넘지 않게 하는 숙련도의 최소값을 찾아내야 한다. 문제는 여기서 발생했다. n개의 문제의 n이 어마무시한 숫자가 아니였다면 do while을 이용해 level을 하나씩 올려보며 언제 딱 limit를 넘지 않는지 확인만 하면 되는 일이었다. 하지만 이 방법으로는 이 문제를 풀 수 없다. n이 커지는 순간 시간초과가 뜨기 때문이다. 알고 싶지 않았다. 그래서 지금 필요한 건 내가 원하는 level의 최소값을 빨리 찾는 방법이다.

 

그래서 탐색 방법들 중 이진 탐색을 사용해보기로 했다. 이진 탐색을 위해 새로운 변수도 만들어 줬다.max_diffs와 min_diffs는 각각 diffs에 담긴 난이도 중 최댓값과 최소값을 갖는다. level이 아무리 커봤자 max_diffs와 min_diffs의 사이이기 때문에 이 값들이 필요했다. 반복문을 시작하면서 used_time을 0으로 초기화하고 level은 max_diffs와 min_diffs의 중간값으로 업데이트한다. 그리고 아까 만들어둔 for문을 돌며 used_time이 몇이 나왔는지 확인한다.

만약 현재 level로 used_time이 limit보다 작을 때, 즉 limit 시간 안에 풀 수 있을 때는 이제 현재 level보다 큰 숙련도는 보지 않기로 한다. max_diffs를 level-1값으로 조정한다. 즉 반을 뚝 잘라서 이제 이비 본 level을 포함하지 않은 그 절반 만큼의 값만 보기로 하는 것이다. 그 절반은 현재 level보다는 작은 값들일 것이다. 현재 level의 숙련도에서도 충분히 풀었으니 이번에는 더 낮은 숙련도에서 풀 수 있는 경우를 찾아보는 것이다.

반대로 현재 level로는 used_time이 limit보다 클 때, 즉 limit 시간 안에 풀 수 없을 때는 현재 level보다 작은 숙련도는 보지 않을 것이다. 그 아래의 숙련도에서는 풀 수 없는 것이 뻔하지 않은가? 그래서 이번에는 min_diffs를 level+1로 조정한다. 방금 본 level을 포함하지 않은채 잘라낸 절반은 현재의 level보다는 큰 수들일 것이다. 현재 level의 숙련도에서는 풀 수 없었으니 이제 그 위에 더 높은 숙련도에서 풀 수 있는 숙련도를 찾아보는 것이다.

이렇게 조정된 max_diffs나 min_diffs를 가지고 다시 반복문으로 올라가면 새로운 max_diffs와 min_diffs로 다시 중간값을 계산하고 그 중간값을 현재의 level로 하여 다시 used_time을 계산할 것이다.

 

이런 과정을 반복하다보면 풀 수 있으면 더 낮은 숙련도로, 풀 수 없으면 더 높은 숙련도로 왔다갔다 하다가 결국 풀 수 있으면서 최소값인 숙련도를 발견하게 된다. 발견하게 되는 순간을 식으로 나타내면 min_diffs>max_diffs 이다. min_diffs와 max diffs가 엇갈리는 순간에 이 반복문을 끝내면 되는 것이다. 따라서 반복문에 들어갈 반복 조건은 min_diffs<=max_diffs 이다. 엇갈리지 않았다면 계속 반복하는 것이다.

 

반복이 끝나는 순간 answer에 min_diffs를 대입하고 answer을 리턴한다. min_diffs를 사용하는 이유는 무엇일까? 사실 이 부분에서 오래 걸렸다. level을 반환하게 하였을 때 어떤 예제는 맞고 어떤 예제는 틀리기도 하기 때문에 어떤 부분에서 틀리는 것인지 알아내야 했다. 반복이 끝나는 순간 level이 최종적인 답을 가리킬거라고 생각했지만 사실 level은 마지막으로 비교한 중앙값이다.

테스트하는 예제 중 성공이 뜨는 예제는 마지막 비교에서 used_time이 limit보다 작게 뜨는 경우, 즉 조건에 충족할 때이다. 그럴 경우 max_diffs가 움직이면서 level과 min은 같은 수에 남게 되는데 그 땐 level을 반환해도 성공이 뜬다.

하지만 만약 마지막 비교에서 조건 불충족이 나온다면 min_diffs가 움직이면서 max_diffs와 level이 같은 자리에 있게 된다. 그러면 level과 min_diffs의 값에 차이가 생기게 된다. 심지어 조건 불충족이 나와 min_diffs가 한 숙련도 위로 올라간 것이기 때문에 이게 정답이 된다. 즉 level은 답이 될 수 없다. 예제로 확인하고 싶다면 입출력 예1을 가지고 확인해보면 된다. max_diffs는 절대로 정답을 가리킬 일이 없기 때문에 더더욱 안된다. 

 

참고 사항

이번 문제에서 이진탐색을 사용하지 않고 그대로 반복문을 돌며 탐색을 하다가 시간초과로 실패가 뜨는 경험을 했다. 이처럼 프로그램의 성능을 높이기 위해 이진탐색으로 코딩을 해야하는 경우들이 있는것 같아 보이는데 이진탐색에 대해서 알아보자.

https://iiblueblue.tistory.com/128

선형 탐색과 이진 탐색

이 문제를 풀다가 선형 탐색과 이진 탐색에 대해서 정리해보았다.

 

 

참고 사항

max_element(iterator start, iterator end)는 어떤 값을 가지는 배열, 벡터, 리스트 등의 [start, end) 범위 중 최댓값을 찾을 때 사용한다. min_element(iterator start, iterator end)는 반대로 최솟값을 찾을 때 사용한다. 사용하기 위해서는 <algorithm> 헤더파일을 포함해야 한다. 반환값은 iterator로 나오기 때문에 각각 최댓값의 위치, 최솟값의 위치를 알려준다. 최댓값과 최솟값의 위치가 아니라 값을 사용하고 싶다면 앞에 *를 붙여 역참조해주면 된다.

#include <algorithm>
...
vector<int> v;
...
int max=*max_element(v.begin(), v.end());
int min=*min_element(v.begin(), v.end());
...

 

 

오답 노트

이진 탐색을 사용하지 않고 while문으로 used_time이 limit보다 작은 순간 바로 숙련도를 리턴하도록 하였다. 하지만 이 경우 입력이 클 땐 시간초과 오류가 발생하게 된다. 따라서 더 빠르게 원하는 값을 탐색할 수 있는 이진 탐색을 사용하여 문제를 해결했다.

이진탐색 후 마지막 값을 반환할 때 level 값을 반환하도록 하였는데 1차이로 계속 오답처리가 되었다. 오답인 경우도 있고 아닌 경우도 있어 왜 그런지 잘 이해할 수 없었는데 다른 사람의 풀이 과정을 보고min_diffs를 반환하는 것으로 수정하였더니 해결되었다.

 

 

문제 링크

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

프로그래머스