코딩 테스트 일기 - 14일 차

디펜스 게임

문제 링크 : 디펜스 게임

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy[i]마리의 적이 등장합니다.
• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  -> 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  -> 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

입출력 예

n	k	enemy	result
7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

풀이 방법

• 해당 문제는 enemy 순서대로 진행할 경우에, 무적권을 언제 사용할지 정하는 것이 가장 포인트인 문제로, 앞에서부터 k개의 무적권을 사용한다고 가정하고, 가장 작은 하나씩 우선순위 큐에서 빼면서 n을 소모하면 될 것으로 보인다.
  -> enemy를 전부 순회한다고 가정하면 O(N)의 시간복잡도와 k개를 넣은 우선순위 큐를 필요로 하기 때문에 O(N*logK)의 시간복잡도가 필요하기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    priority_queue<int, vector<int>, greater<int>> PQ;
    int answer = 0;
    
    for(int i : enemy){
        PQ.push(i);
        
        if(PQ.size() > k){
            int small = PQ.top(); PQ.pop();
            n -= small;
            
            if(n < 0)
                break;
        }
        answer++;
    }

    return answer;
}

---

우박수열 정적분

문제 링크 : 우박수열 정적분

문제 설명

콜라츠 추측이란 로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측으로 모든 자연수 k에 대해 다음 작업을 반복하면 항상 1로 만들 수 있다는 추측입니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.

예를 들어 주어진 수가 5 라면 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒2 ⇒ 1 이되어 총 5번만에 1이 됩니다.

수가 커졌다 작아지기를 반복하는 모습이 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습과 비슷하다고 하여 우박수 또는 우박수열로 불리기도 합니다. 현재 이 추측이 참인지 거짓인지 증명되지 않았지만 약 1해까지의 수에서 반례가 없음이 밝혀져 있습니다.

은지는 우박수열을 좌표 평면 위에 꺾은선 그래프로 나타내보려고 합니다. 초항이 k인 우박수열이 있다면, x = 0일때 y = k이고 다음 우박수는 x = 1에 표시합니다. 이런 식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 다음과 같이 꺾은선 그래프를 만들 수 있습니다.

은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다. x에 대한 어떤 범위 [a, b]가 주어진다면 이 범위에 대한 정적분 결과는 꺾은선 그래프와 x = a, x = b, y = 0 으로 둘러 쌓인 공간의 면적과 같습니다. 은지는 이것을 우박수열 정적분이라고 정의하였고 다양한 구간에 대해서 우박수열 정적분을 해보려고 합니다. 0 이상의 수 b에 대해 [a, -b]에 대한 정적분 결과는 x = a, x = n - b, y = 0 으로 둘러 쌓인 공간의 면적으로 정의하며, 이때 n은 k가 초항인 우박수열이 1이 될때 까지의 횟수를 의미합니다.

예를 들어, 5를 초항으로 하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 점들을 연결하면 꺾은선 그래프가 나옵니다. 이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.

우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.

제한 사항

• 2 ≤ k ≤ 10,000
• 1 ≤ ranges의 길이 ≤ 10,000
  -> ranges의 원소는 [a, b] 형식이며 0 ≤ a < 200, -200 < b ≤ 0 입니다.
• 주어진 모든 입력에 대해 정적분의 결과는 227 을 넘지 않습니다.
• 본 문제는 정답에 실수형이 포함되는 문제입니다. 입출력 예의 소수 부분 .0이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.

입출력 예

k	ranges	result
5	[[0,0],[0,-1],[2,-3],[3,-3]]	[33.0,31.5,0.0,-1.0]
3	[[0,0], [1,-2], [3,-3]]	[47.0,36.0,12.0]

풀이 방법

• 해당 문제는 콜라츠 추측을 기반으로 정적분을 구하는 문제인데, ranges 범위에 있는 정적분 값을 모두 구해야 하기 때문에, 콜라츠 추측 값을 기반으로 미리 넓이를 구해서 저장해놓은 다음에, ranges에 따른 정적분 값을 더해가면서 답을 구할 것이다.
  -> 콜라츠 추측을 하는 데 n이 몇까지 갈지는 모르겠지만, 이것은 범위 내에 될 것이기 때문에 이 부분에 대한 시간복잡도는 생각하지 않았다. ranges의 원소 최대 값이 200이라고 하는 것을 보니 콜라츠 추측은 200이 최대지 않을까 싶기도 하다.
  -> ranges의 길이만큼 다 순회를 해야 하고, 원소 최대 값이 200이기 때문에 N은 ranges의 길이, K는 원소 최대값이라고 할 때, O(N*K)의 시간복잡도가 걸릴 것으로 추정되기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

vector<double> solution(int k, vector<vector<int>> ranges) {
    // 구간 별로 모든 넓이 구하기
    vector<double> extent;
    
    while(k != 1){
        int temp = k;
        if((k & 1) == 1){   // 홀수
            k = k * 3 + 1;
        }else{              // 짝수
            k /= 2;
        }
        extent.push_back((double)(temp + k) / 2);
    }
    
    int n = extent.size();
    
    // ranges 별로 정적분 값 구하기
    vector<double> answer;
    
    for(vector<int> v : ranges){
        double sum = 0;
        if(v[0] > n + v[1]){
            answer.push_back(-1.0f);
            continue;
        }
        
        for(int i = v[0]; i < n + v[1]; i++){
            sum += extent[i];
        }
        answer.push_back(sum);
    }
    
    return answer;
}