[CodeKata] 프로그래머스: 10.17(일), 금과 은 운반하기

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

정말 자괴감이 들 정도로, Level 3 대부분의 문제들을 풀지 못하고 있다.

좋은 풀이중에, 이분탐색 알고리즘으로 비교적 간단하게 푼 예시를 코드분석하고, 이분탐색에 대해 좀 더 공부해보고자 한다.

 

🖇 리뷰

function solution(a, b, g, s, w, t) {
    let answer = 10e5 * 4 * 10e9;
    
    let start = 0;
    let end = 10e5 * 4 * 10e9;
    
    while( start <= end) {
        let mid = Math.floor((start + end) / 2);
        let gold = 0;
        let silver = 0;
        let add = 0;
        
        for( let i =0; i < s.length; i++ ) {
            let now_g = g[i];
            let now_s = s[i];
            let now_w = w[i];
            let now_t = t[i];
            
            let move_cnt = Math.floor(mid / (now_t * 2));
            if(mid % (now_t * 2) >= t[i]) move_cnt++;

            gold += (now_g < move_cnt * now_w) ? now_g : move_cnt * now_w;
            silver += (now_s < move_cnt * now_w) ? now_s : move_cnt * now_w;
            add += (now_g + now_s < move_cnt * now_w) ? now_g + now_s : move_cnt * now_w;
        }
        
        
        if(gold >= a && silver >= b && add >= a + b) {
            end = mid - 1;
            answer = Math.min(mid, answer);
        }else {
            start = mid + 1;
        }
    }
    
    return answer;
}

* 출처 : https://redbinalgorithm.tistory.com/696

 

1. 이분탐색 알고리즘 위한 start/end 설정

• 먼저, 이분탐색을 위해 start 는 최소값 0, end 는 최대값인 10^9 * 4 * 10^5 로 설정한다.
• 최대값이 위와 같은 이유는, 최대 필요량(10^9) * 최소무게(1) * 최대시간(10^5) * 금은 각각 2번씩 왕복의 이유이다.
• answer는 최소(최적) 시간으로 비교하기 위해 우선 최대값과 동일하게 설정한다. (start-end 절반인 mid와 비교)
• 이분탐색 알고리즘은 start 혹은 end가 mid값으로 갱신되며, start <= end 를 만족하지 않으면 둘은 만나므로 이 때 while 반복문이 종료된다. 

 

2. 이분탐색 알고리즘 케이스 설정

• mid는 (start + end) 의 중간값이다. 또한, gold, silver, add 는 특정시간에 얻을 수 있는 금, 은, 금/은 의 양이다.
• 다음으로, 인덱스를 순환하며 현재 마을의 now_g(금 보유량), now_s(은 보유량), now_w(옮기는 양), now_t(옮기는 시간) 을 각각 설정한다.
• move_cnt는 현재 마을에서 옮길 수 있는 총 횟수이다. 왕복이므로 (now_t * 2) 로 현재시간(mid)를 나눈 값을 버림(floor)한다. 만약, 위 경우의 나머지가 now_t보다 크다면 1번 편도가 가능하므로 move_cnt 에 1을 더하는 것이다.
• gold, silver, add 에 각각 더하는 값은, 보유량(now_g, now_s)과 왕복으로 옮기는 총량(move_cnt * now_w) 중 최소값이다.
• 이 과정을 모든 순환에 반복하면, 해당시간(mid)에서 모든 마을에서 옮길 수 있는 gold, silver, add(금+은) 총량이 나온다.

 

3. 이분탐색 알고리즘 케이스 검증

• 먼저, gold가 목표량(a) 이상, silver가 목표량(b) 이상, gold + silver가 (a+b) 이상이면 모두 옮길 수 있는 충분한 시간이다.
• 이 땐, 최소값을 탐색하기 위해 end 값을 (mid - 1) 로 줄여준다. answer 역시, 현재 answer과 mid 중 더 작은값으로 갱신한다.
• 만족하지 않다면, 더 많은 시간이 요구되므로 start 값을 (mid + 1) 로 늘려준다.
• 이 과정을 반복하면 조건을 만족하는 시간대로 start - end 가 좁혀지며, 그 사이에서 최소값으로 갱신하면서 목표시간값에 도달한다.

---

항상 목표시간을 탐색하는데 있어 많은 방법을 고민했다. 최소시간값을 누적할지, 최대공약수/최소공배수 등으로 검증해볼지 등등..

하지만, 이전에도 느꼈듯 이분탐색이 가장 적합한 방법이다. 1(분, 시간 등) 단위인 시간값을 검출하기 위해서는 이 방법이 효율적인 것이다.