[프로그래머스] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 C#

 

문제 설명

 

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

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

프로그래머스

 

문제 해결

for 문을 돌려 최솟값을 구하고자 함 -> 15번 문제부터 시간 초과로 실패

-> 이진탐색을 이용하여 최솟값, 최댓값을 중간값으로 구하려고 함 -> 성공

 

1. 이중 for문 (실패)

using System;

public class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        
            int wrongCnt = 0; //틀린 횟수
            int time_prev = 1; //이전 퍼즐의 소요시간

            long totalTime = 0;
        
          for (int i = 1; i < limit; i++)
            {
                totalTime = 0;
                time_prev = 1;

                for (int j = 0; j < diffs.Length; j++)
                {
                    if(j > 0)
                    {
                        time_prev = times[j];
                    }

                    //현재 숙련도보다 퍼즐의 난이도가 높은 경우
                    if (i < diffs[j])
                    {
                        wrongCnt = diffs[j] - i;
                        totalTime += (time_prev + times[j-1]) * wrongCnt + times[j];
                    }
                    else
                    {
                        totalTime += times[j];
                    }
                }


                //총 소요시간이 제한시간보다 크면 컨티뉴
                if (totalTime > limit)
                {
                    continue;
                }
                else
                {
                    answer = i;
                    break;
                }
            }
          
        return answer;
    }
}

 

2. 이진탐색

using System;
using System.Linq;

public class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
      
				 int wrongCnt = 0; //틀린 횟수
            int time_prev = 1; //이전 퍼즐의 소요시간

            long totalTime = 0;

            int min = 1;
            int max = diffs.Max();

            int median = 0; //중간값 찾기

            while (min <= max)
            {
                median = (min + max) / 2; //중간값 찾기

                totalTime = 0;

                for (int j = 0; j < diffs.Length; j++)
                {
                    time_prev = j == 0 ? 1 : times[j];   //첫번째일 경우 이전 소요시간은 1

                    totalTime += times[j];

                    //현재 숙련도보다 퍼즐의 난이도가 높은 경우
                    if (median < diffs[j])
                    {
                        totalTime += (time_prev + times[j - 1]) * (diffs[j] - median);

                        if (totalTime > limit)
                        {
                            break;
                        }
                    }
                }

                if (totalTime > limit)  //총 소요시간이 제한시간보다 클 경우
                {
                    min = median + 1;
                }
                else
                {
                    max = median - 1;
                }
            }

            answer = min;
        return answer;
    }
}