프로그래머스, 퍼즐 게임 챌린지 C++

About this offer

문제 사이트 링크 풀이 과정 최솟값 구하기 + 브루트 포스 느낌의 문제이다. 일단은 2가지의 구현 방법이 떠올랐다 무식하게 순회, 브루트 포스 1부터 level를 차례대로 순회하면서 최솟값 구하기 + 도달했을 때 return 하는 것이다. 근데 과연 제한 시간 내로 풀 수 있는가? 입출력 예시만 보더라도 최악의 경우 30만 * 10^15 가 보인다. 그래도 뭔가 가능할 것 처럼 보이지만, long long limit 이라는 함정이 있어. 퍼즐은 순서대로 푸는 거라 정렬하면 안된다. 투 포인터? 어쨌든 level의 상한선은 무조건 있다. diff의 최대 값 정도 겠지라는 생각이 든다. 오히려 평균?값을 구하면서 근접하는 느낌인 것 같다. 일단은 알고리즘을 너무 오랫만에 푸는 거라 1번 방법으로 풀어보았다. #include <iostream> #include <string> #include <vector> using namespace std; int diff, time_cur, time_prev, limit; // diffs_len은 배열 diffs의 길이입니다. // times_len은 배열 times의 길이입니다. int solution(vector<int> diffs, vector<int> times, long long limit) { int answer = 0; while (true) { // 최솟값, 커트라인을 구하기 위해 true. 구하면 false long total_time = 0; answer++; // diffs[0]은 항상 1 total_time += times[0]; time_prev = times[0]; for (int i = 1; i < diffs.size(); i++){ time_cur = times[i], time_prev = times[i-1]; if (answer < diffs[i]) { // level이 더 낮으면 (diff-level) * (time_cur + time_prev) + time_cur 로 다시 풀 수 있음 total_time += (diffs[i]-answer) * (time_cur+time_prev) + time_cur; } else { // level이 더 높다면 time_cur total_time += time_cur; } if (total_time > limit) { // 쓸데 없는 순회 방지. break; } } // 현 숙련도 기준 판별 if (total_time <= limit){ // cout << "level: " << answer << ", total time: " << total_time << "\n"; break; } } // 제한 시간 내에 퍼즐을 모두 해결하기 위한 "숙련도의 최솟값"을 구하려고 합니다 return answer; } 결과 & 근거 결과는 성공 공식 도출은 비교적 빠르게 됐다. 숙련도가 높으면? times[i] 만큼 소요 숙련도가 낮은 경우 (diffs[i] - level) * (times[i] + times[i-1]) + times[i] 만큼 소요 첫 제출에서 21케이스 중 5개 실패(71.5점)가 났다. 원인을 분석하던 중 내부 루프에서 total_time이 limit을 초과하면더 순회할 필요가 없다는 것을 깨달았다. if (total_time > limit) break; 를 추가하자 전체 통과됐다. 풀이 총 소요 시간 약 30분. 단, 완전탐색 + early break 구조라 이론상 TLE 범위 (O(max_diff × n)). 통과한 이유는 inner break가 저레벨 구간에서 조기 종료를 유발했기 때문이다. (운 적인 요소라고도 할 수 있을 듯 하다) 정석 풀이는 f(level)의 단조 감소 특성을 이용한 이분탐색이다. O(n × log(max_diff))로 근본적으로 효율적인 접근이었다. auto calc = [&](long long lv) -> long long { long long total = times[0]; for (int i = 1; i < (int)diffs.size(); i++) { if (lv < diffs[i]) total += (long long)(diffs[i]-lv) * (times[i]+times[i-1]) + times[i]; else total += times[i]; if (total > limit) return total; // early break 유지 } return total; }; int lo = 1, hi = *max_element(diffs.begin(), diffs.end()); while (lo < hi) { int mid = (lo + hi) / 2; if (calc(mid) <= limit) hi = mid; // 가능하면 더 낮추기 else lo = mid + 1; // 불가능하면 더 올리기 } return lo; 알고리즘 분류 이분탐색 시뮬레이션 파라메트릭 서치

Offer details

Provider

velog

Source

velog-rss

Score

54.39

Confidence