[프로그래머스 C#] Lv.2 퍼즐게임 (PCCP 기출문제 2번)

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

프로그래머스

 

1. 정답코드 및 핵심 아이디어, 유의사항

제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최소 값을 찾는 문제

- 난이도에서 숙련도를 뺀 값이 현재 퍼즐을 틀리는 횟수가 됨

- 퍼즐을 틀리는 여부에 관계 없이 퍼즐을 푸는 시간은 무조건 드는 시간

- 현재 퍼즐을 틀릴 경우 이전 퍼즐을 다시 풀어야 함

 -> ( 이전 퍼즐 풀이 시간 + 현재 퍼즐 풀이 시간 ) * 틀리는 횟수

+ 이진 탐색 ( 최적화 )

 

코드 참조

using System;
using System.Linq;

public class Solution
{
    public bool IsClear(ref int[] diffs, ref int[] times, long limit, int level)
    {
        limit -= times[0];
        
        for(int i = 1; i < diffs.Length; i++)
        {
            limit -= times[i];
            int count = diffs[i] - level;
            
            if(count > 0)
                limit -= count * (times[i - 1] + times[i]);
            
            if(limit < 0)
                return false;
        }
        
        return true;
    }
    
    public int solution(int[] diffs, int[] times, long limit)
    {
        int left = 1;
        int right = diffs.Max();
        
        while(left <= right)
        {
            int mid = (left + right) / 2;
            
            if(IsClear(ref diffs, ref times, limit, mid))
                right = mid - 1;
            else
                left = mid + 1;
        }
        
        return left;
    }
}