이 포스팅에서는 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 카카오 블라인드 채용 외벽 점검
AI AI Agent들이 어느 정도 유용한 건 맞지만, 생각보다 성능이 그렇게 시원찮은지는 모르겠다. 특히나 코드…
티앤미미 예약이 그렇게 힘들다는 티앤미미를 처남네가 운좋게 예약해서 어제 저녁 다녀왔다. 딤섬이 그렇게 맛있다고 하는데,…
아난티 부산 시설과 고객 서비스가 이렇게 극단적으로 다른 방향인 호텔이 있을까 싶다. 시설의 퀄리티는 5성급이라기에…
This website uses cookies.