이 포스팅에서는 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[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][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 카카오 블라인드 채용 외벽 점검
Planning A well-structured plan has the following characteristics: First, the ultimate vision you aim to…
English The most common problem for English learners like myself is that we often use…
This website uses cookies.