문제 설명
당신은 순서대로 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의 시간을 사용하므로 총 6 × 2 + 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
- 1 ≤ limit ≤ 1015
입출력 예
diffs | times | limit | result |
[1, 5, 3] | [2, 4, 7] | 30 | 3 |
[1, 4, 4, 2] | [6, 3, 8, 2] | 59 | 2 |
[1, 328, 467, 209, 54] | [2, 7, 1, 4, 3] | 1723 | 294 |
[1, 99999, 100000, 99995] | [9999, 9001, 9999, 9001] | 3456789012 | 39354 |
입출력 예 설명
입출력 예 #1
숙련도가 3인 경우 다음과 같이 진행됩니다.
- 1번째 퍼즐을 2의 시간을 사용하여 해결합니다.
- 2번째 퍼즐을 5 - 3 = 2번 틀려서 총 (4 + 2) × 2 + 4 = 16의 시간을 사용하여 해결합니다.
- 3번째 퍼즐을 7의 시간을 사용하여 해결합니다.
총 2 + 16 + 7 = 25의 시간을 사용하여 모든 퍼즐을 해결할 수 있습니다. 숙련도가 3보다 작은 경우 제한 시간인 30 이내에 모든 퍼즐을 해결할 수 없습니다.
따라서 3을 return 해야 합니다.
문제풀이
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
bool limitTime(int diffs[], size_t diffs_len, int times[], size_t times_len, long long limit, int level) {
long long sum = 0;
for (int j = 0; j < diffs_len; j++) {
if (diffs[j] <= level) {
sum += times[j];
} else {
sum += (times[j] + times[j - 1]) * (diffs[j] - level) + times[j];
}
}
if (sum > limit) {
return false; //총 시간이 제한시간을 넘으면 실패처리
}
return true;
}
// diffs_len은 배열 diffs의 길이입니다.
// times_len은 배열 times의 길이입니다.
int solution(int diffs[], size_t diffs_len, int times[], size_t times_len, long long limit) {
int answer = 0;
int min = 1;
int max = 0;
// 최대 난이도 찾기
for (int i = 0; i < diffs_len; i++) {
if (max < diffs[i]) {
max = diffs[i];
}
}
// 이진 탐색
while (min <= max) {
int mid = (min + max) / 2;
if (limitTime(diffs, diffs_len, times, times_len, limit, mid)) {
answer = mid; // 가능한 숙련도를 기록
max = mid - 1; // 더 낮은 숙련도를 탐색
} else {
min = mid + 1; // 더 높은 숙련도를 탐색
}
}
return answer;
}
처음에는 level 1부터 시작하여 높아지는 방식으로 제한시간안에 해결 했을 경우 답으로 도출하였는데, 이 방법으로 제출하니 케이스 14번 이후거는 시간 초과로 실패처리되었다. 하여, 하나씩 찾는 방법은 시간이 오래걸리니 이를 해결하기 위해 이진탐색을 이용하여 숙련도를 최소 최대를 지정하여 중간 값을 찾고 최소한의 숙련도를 찾았다. 이렇게 답을 찾을 수 있지만 시간복잡도까지 고려해야 하는 것도 중요한 것 같다.
'프로그래머스 풀이' 카테고리의 다른 글
[SQL] 대장균의 크기에 따라 분류하기 1 (2) | 2025.01.03 |
---|---|
[c++]나누어 떨어지는 숫자 배열 (2) | 2024.12.09 |
[c++]핸드폰 번호가리기 (0) | 2024.12.06 |
[c++]부족한 금액 계산하기 (0) | 2024.12.03 |
[c++][javascript]아이스아메리카노 (0) | 2024.11.28 |