오늘 배운 것들
알고리즘 문제 풀이
- 어피치와 라이언이 양궁 대회를 실시한다.
- 라이언이 1 ~ 10점에서 어피치가 a 발을 맞췄고 라이언이 b발을 맞췄을 때, a ≤ b일 경우에만 해당 점수를 얻을 수 있다.
- 최종 점수가 더 높은 선수로 우승자를 결정한다.
- 라이언이 우승할 경우가 있는 경우, 어피치와 가장 큰 점수 차이로 이길 수 있어야 한다.
- 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 반환한다.
키 포인트
- 비트마스킹을 이용한 완전 탐색
- 처음에는 그리디로 풀려고 하였으나, 그리디로 해결할 경우 답도 없어 보여서 완전 탐색으로 진행했다.
- 비트마스킹과 배열을 혼합하여 사용할 경우 인덱스 주의
- 해당 문제 때문에 많은 시간을 소비했다.
해결 방법
우선 완전 탐색을 할 방법을 찾는다.
dfs로 해결하는 방식도 괜찮지만, 문득 라이언이 이겨야만 하는 경우에 대해 해당 위치를 지정하고, 조건을 만족할 수 있는지 확인하는 방법을 사용하면 되지 않을까? 라고 생각하였다. 따라서 이긴 경우 비트를 1, 졌을 경우 비트를 0으로 두어 모든 경우에 대하여 탐색했다. 현재 경우 총 배열의 길이가 11이므로 2 ** 11 = 2048가지의 경우만 존재할 수 있으므로 탐색에 대하여 문제될 것이 없다. (배열의 길이가 짧기 때문에 완전 탐색을 시도해 보라는 문제의 의도도 알 수 있다)
1: 라이언이 해당 점수를 어피치보다 많이 맞춰서 점수를 가져오는 경우
0: 라이언이 해당 점수를 가져올 수 없는 경우
비트를 사용하여 모든 경우를 탐색하는 방법은 다음과 같다.
for i in range(1 << 11): # 2048가지의 경우에 대하여 탐색
for j in range(11):
if (1 << j) & i:
# do something해당 비트 연산자에서의 조건을 만족할 수 있는지 확인한다.
확인 하는 과정은 비트가 1인 위치에서 어피치가 해당 점수에서 맞춘 화살의 개수 + 1을 모두 더하고, 모두 더한 값이 n을 초과한다면 불가능한 경우의 수 이므로 해당 경우는 기록하지 않는다.
비트를 배열로 변환한다.
배열을 반환하기 위해서는 비트를 배열로 바꿔야 한다.
변환한 배열의 합이 n이 되는지 확인한다.
배열의 합이 n이라면, n개의 화살을 전부 명중시켰다는 뜻으로 다른 위치에 화살을 맞출 필요가 없으므로 다음단계로 이동한다.
- 배열의 합이 n 미만이라면, n개의 화살을 소모하기 위하여 다른 곳에 화살을 쏴야 한다. 비트마스킹을 선언했을 때 정의를 생각해보면, 내가 이겨야만 하는 곳을 1로 표현한다고 했다. 필요한 곳은 이미 내가 이겨야만 하는 곳에 전부 명중시켰기 때문에, 나머지에 대하여 가장 작은 곳에 넣어주면 된다.
- 모든 경우를 탐색하므로, 최대의 차를 내어 이길 수 있는 경우 역시 포함되어 있다. 만약 명중시킨 화살의 개수가 n보다 적어서 가장 작은 쪽에 명중을 시켰을 때 해당 경우가 최대의 차를 낼 수 있는 방법이라 하더라도, 비트마스킹 방식으로 탐색하면서 해당 경우가 포함되어 있으므로, 그 부분에 대해서는 신경 쓸 필요 없이 비어있는 곳에 넣어줘도 된다.
나머지는 코드로 확인하자.
코드 보기
INF = 987654321
def solution(n, info):
max_score = 0
case = INF
score_board = [0] * 11
for i in range(1 << 11):
count = 0
for j in range(11):
if (1 << j) & i:
count += info[10 - j] + 1
if count > n:
continue
next_score = calculate(info, i)
next_score_board = transform(info, i)
s = sum(next_score_board)
if s < n:
for i in range(10, -1, -1):
if next_score_board[i] == 0:
next_score_board[i] += n - s
break
if next_score > max_score:
max_score = next_score
case = i
score_board = next_score_board[:]
elif next_score == max_score:
score_board = compare(score_board, next_score_board)
if case == INF:
return [-1]
return score_board
def calculate(info, score_board):
a, b = 0, 0
for i in range(11):
if (1 << i) & score_board:
a += i
elif info[10 - i] > 0:
b += i
return a - b
def transform(info, score_board):
ret = [0] * 11
for i in range(11):
if (1 << i) & score_board:
ret[10 - i] = info[10 - i] + 1
return ret
def compare(prev, next):
for i in range(10, -1, -1):
if prev[i] > next[i]:
return prev
if prev[i] < next[i]:
return next
return [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
n = 10
info = [0,0,0,0,0,0,0,0,3,4,3]
print(solution(n, info))느낀 점
- 이 문제를 처음 보면서 느낀 점은 이게 2단계라고..? 라는 생각이었다. 며칠이 걸려서 문제를 해결했는데 돌아오는 것은 고작 1점… ㅋㅋㅋ 카카오가 들어가기 이렇게 빡세다 …
- 위에서 서술한 키 포인트 2번의 인덱스 문제로 많은 시간을 소비했다. 비트 마스킹은 배열로 놓고 생각했을 때 뒤에서부터 인덱스를 탐색하는 것과 동일하다. 그러나, 해당 부분을 까먹고 배열로 처리할 때도 똑같이 인덱스를 사용하여 잘못된 답이 나왔고, 이를 인지하기 까지 많은 시간이 걸렸다.
for j in range(11):
if (1 << j) & i:
count += info[10 - j] + 1 # 정답
for j in range(11):
if (1 << j) & i:
count += info[j] + 1 # 오답앞으로는 배열과 비트마스킹을 혼합하여 사용할 경우 좀 더 세심한 고려를 해야겠다.
- 해당 코드가 완벽하게 맘에 드는 것은 아니다. 일단
case변수의 모호성(일단 조건을 하나라도 만족하는지를 판별하기 위하여 사용되고 있지만, 해당 조건은 한 번 밖에 사용되지 않음), 그리고 max_score과 배열의 진짜 score간의 차이가 존재할 수 있다는 것이다. 다른 방법으로 해결할 수 있는지 조금 더 고민해 봐야겠다.
