[Programmers] 월간 코드 챌린지 - 금과 은 운반하기

hzw94·2021년 9월 14일
0

ProblemSolving

목록 보기
9/9

후기

역시나, 이분탐색이 첨가된 문제는 이분탐색 개념 자체가 어려운게 아니라 이 문제가 이분탐색으로 풀릴까? 라는 생각을 하게 되는 과정이 어렵다.

월코챌 풀다가 중간에 전화때문에 못풀었는데, 풀어보니 굉장히 좋은 문제다.
올해 2021 카카오 인턴십 마지막 문제가 생각나고, 실제 기업 코딩테스트에서 어렵게 내고자 하면 선택하기 좋은 주제라고 생각한다.

이런 유형은 취준생이라면 꼭 풀어보길 권장한다.

문제 설명

문제의 링크는 여기 에 있다.

대략 왕국에 도시들이 있고,
도시를 짓기 위해서 금이랑 은을 전달해야 하는데
도시를 짓기 위해 필요한 금과 은의 양을 가장빠르게 전달할수 있는 시간에 대해 물어보고 있다.

가장 나이브한 풀이는 아무래도 시간을 늘리면서 언제 금과 은이 다 채워지는지 보는 방법이 있겠지만
이러한 방법으로는 대략 최대 10의 14승 이상의 값을 하나하나 보면서 탐색하는것은 그다지 문제 해결에 도움되지 않는다.

그렇다면 어떻게 풀어봐야할까?

탐색해야할 것이 굉장히 많을때 항상 하는것이 세가지가 있는데

  1. 규칙성이 있는지?
  2. 근사치를 통해 정답을 구할수 있는지?
  3. 어차피 모두 탐색해야 한다면 탐색 구간을 줄일수 있는지?

정도 겠다.
문제를 풀면서 특정 룰에 따른 규칙성을 찾지 못했고, 그리디 문제도 아니였기에 이분탐색을 선택했다.

시간에 따라 이분탐색을 하면서,
끝 시간에 따라 금과 은에 따로 모두 넣었을때와, 순수한 총량의 비교를 통해 가장 최적의 지점이 어디있는지 확인할수 있는 문제다.

C 코드를 통해 보면

#include <stdio.h>

#define MIN(a, b) a < b ? a : b
typedef long long ll;

long long solution(int a, int b, int g[], size_t g_len, int s[], size_t s_len, int w[], size_t w_len, int t[], size_t t_len) {
    ll start = 0;
    ll end = 1e16;
    int i = 0;
    while (start < end) {
        ll mid = (start + end) / 2;

        int totalSum = 0;
        int Gold = 0;
        int Silver = 0;

        for (i = 0; i < g_len; i++){
            if(mid >= t[i]) {
                ll Remain = mid - t[i];//마지막 운전 할만큼 뺴주기
                ll time = ((Remain / 2) / t[i]) + 1;// 운전 횟수
                totalSum += MIN(time * w[i], g[i] + s[i]);
                Gold += MIN(time * w[i], g[i]);
                Silver += MIN(time * w[i], s[i]);
            }
        }
        if (totalSum >= (a + b) && Gold >= a && Silver >= b) {
            end = mid;
        }else {
            start = mid + 1;
        }
    }
    return start;
}

정도가 될것 같다.

Swift 코드

import Foundation

func solution(_ a:Int, _ b:Int, _ g:[Int], _ s:[Int], _ w:[Int], _ t:[Int]) -> Int64 {
    var start = 0
    var end = Int(1e15)
    while start < end {
        let mid : Int = (start + end) / 2
        
        var sum = 0
        var gold = 0
        var silver = 0
        
        for i in 0..<g.count {
            if mid >= t[i] {
                let rm = mid - t[i]
                let time : Int = ((rm / 2) / t[i]) + 1
                sum += min(time * w[i], g[i] + s[i])
                gold += min(time * w[i], g[i])
                silver += min(time * w[i], s[i])
            }
        }
        
        if sum >= a + b, gold >= a, silver >= b{
            end = mid
        }else{
            start = mid + 1
        }
    }
    
    return Int64(start)
}
profile
볼가놈의 iOS & Swift & RxSwift & PS 저장창고

0개의 댓글