[카카오] 2020 KAKAO BLIND RECRUITMENT 1차 풀이 – 외벽 점검

Posted on by

이 포스팅에서는 2020 카카오 블라인드 채용 1차 문제인 ‘외벽 점검’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/60062에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.

공식 풀이는 링크를 참조하시기 바랍니다.

외벽 점검

출처 : 2020 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/60062
카테고리 : Dynamic
난이도 : 보통

문제 요약

시계 방향으로 weak point들이 주어지고, 프렌드들의 연료가 주어진다. 연료 1당 1의 거리를 이동할 수 있다. 모든 weak point들을 커버하기 위해 필요한 프렌드들의 최소 숫자를 구하여라.

문제 풀이

프렌즈 상태

가능한 프렌드들이 N명 이라고 할 때 N개의 비트를 통해 상태를 표현한다. 예를 들어 8명의 프렌드들이 있다고 할 때 0번, 3번, 7번 프렌드가 사용되었다고 하면 01001001로 표현할 수 있다. 정수로 나타낼 때 i번 프렌드는 2 ** i와 같은 값을 가진다고 생각할 수 있다

DP 테이블의 정의 및 초기화

DP[i][j]는 0 ~ i번째 weak point들을 프렌즈 상태 j로 커버할 때 남길 수 있는 연료의 최대값이다.

맨 처음 weak point는 그 전에 아무것도 없으므로 무조건 프렌드 한 명을 놔야만한다. 따라서 DP[i][j] = dist[k] (j = 2 ** k, k는 0 ~ 프렌드 수 – 1)가 된다.

i > 0인 경우에 대해서 DP[i][j]의 j는 i – 1번째 weak point의 어떤 상태로부터 온다. 두 가지 경우가 있다.

  • DP[i – 1][j]에서 남은 연료를 써서 i번째 weak point에 도달한다.
  • DP[i – 1][x]에서 어떤 프렌드를 새로 추가해서 weak point에 도달한다.
    • 이 때 k번째 프렌드를 추가하기 위해서 j의 k번째 비트는 반드시 1이어야 한다.
    • 이 경우 x는 j xor (2 ** k)가 된다.

위 경우들 중에서 가장 연료를 많이 남겨먹는 것이 DP[i][j]의 자리를 차지한다.

수행을 모두 마치고 난 후에 마지막 weak point의 인덱스 M에 대해 DP[M][j]의 값들 중에서 도달이 가능한 j들 중에서 비트에 존재하는 1의 갯수가 가장 적은 것이 정답이다.

회전 연산

어떤 해의 경우에는 주어진 weak point들의 0번째에서 시작하는 것이 아니라 임의의 지점에서부터 출발해서 한 바퀴를 돌아서 0번째 weak point를 커버하는 것이 더 최적인 것들도 있다.

따라서 모든 weak point들에 대해 각 지점을 출발점으로 잡고 DP를 수행한 결과들 중에서 가장 작은 값을 출력해야한다.

정답 코드

def count_people(number):
    cnt = 0
    while number > 0:
        cnt += number % 2
        number //= 2
    return cnt
 
def process(weak, dist, dp):
    K = []
    for i in range(len(dist)):
        K.append(2 ** i)
        # initial position is always zero
        dp[0][K[i]] = dist[i]
        
    for i in range(1, len(weak)):
        for j in range(len(dp[0])):
            # move from previous state without adding people
            if dp[i – 1][j] >= weak[i] – weak[i – 1]:
                dp[i][j] = dp[i – 1][j] – (weak[i] – weak[i – 1])
            
            # add people from possible previous state
            for k in range(len(dist)):
                if j & K[k] == K[k] and dp[i – 1][j ^ K[k]] >= 0:
                    dp[i][j] = max(dp[i][j], dist[k])
            
    answer = len(dist) + 1
    for j in range(len(dp[0])):
        if dp[len(weak) – 1][j] >= 0:
            new_answer = count_people(j)
            answer = min(answer, new_answer)
            
    return answer != len(dist) + 1 and answer or –1
            
def solution(n, weak, dist):
    k = 2 ** len(dist)
    answer = –1
    for i in range(len(weak)):
        # set this position as start position
        new_weak = [0] * len(weak)
        pivot = weak[i]
        for j in range(i, len(weak)):
            new_weak[j – i] = weak[j]– pivot
        for j in range(i):
            new_weak[j + len(weak) – i] = weak[j] + n – pivot
        
        # DP
        dp = [[–1] * k for j in range(len(new_weak))]
        new_answer = process(new_weak, dist, dp)
        if new_answer != –1:
            answer = answer == –1 and new_answer or min(answer, new_answer)
            
    return answer
cs

Competition 카카오 블라인드 채용 외벽 점검