🔗
풀이
이 블로그의 풀이를 참고했다.
라이언의 화살 배열을 구성할 수 있는 경우의 수는 아래와 같이 3가지다
- 어피치가 쏜 과녁에 라이언이 쏠 경우
- 어피치가 쏘지 않은 과녁에 라이언이 쏠 경우
- 어떤 과녁이든 쏘지 않고 넘어가는 경우
🍑 어피치가 쏜 과녁인 경우
어피치가 쏜 과녁에서 점수을 내려고 하는 경우, 라이언은 어피치가 쏜 화살의 개수보다 더 많은 개수의 화살을 쏴야 한다. 점수 격차를 크게 벌이는 게 중요하기 때문에 화살의 개수는 아낄수록 좋고, 어차피 1개든 2개든 화살의 개수가 많기만 하면 점수를 딸 수 있으므로 어피치의 화살 개수+1개만 쏘면 된다.
어피치가 쏘지 않은 과녁인 경우
라이언이 점수를 내려면 1개의 화살만 쏴도 된다. 점수도 해당 과녁의 점수만 추가하고, 화살의 개수도 1개만 빼준다.
라이언이 화살을 쏘지 않는 경우
다음 인덱스로 바로 넘어가면 된다.
어피치와 라이언의 점수 차이
어피치와 라이언의 점수 차이를 구해야 하는 문제이므로 두 점수 차이를 계속 값으로 가져가면 된다. 라이언의 점수에서 어피치의 점수를 빼주면 되기 때문에 라이언이 얻게 되는 점수를 계속해서 양수로 더해나가고, 어피치가 얻는 점수는 음수로 빼나가면 된다.
어피치의 점수는 이미 정해져 있고, 매 연산마다 빼주는 것은 번거롭기 때문에 미리 어피치가 얻을 수 있는 점수를 모두 구해서 음수로 미리 저장해둔다. score 변수에 저장했다.
어피치가 얻은 점수를 음수로 미리 설정해뒀기 때문에 어피치가 점수를 잃게 될 경우는 반대로 양수로 더해줘야 한다.
이제 매 연산마다 라이언이 점수를 얻거나 어피치가 점수를 잃으면 점수를 더해나가기만 하면 된다. 두 가지 경우가 동시에 일어난다면 두 번 더해준다.
종료 조건
탐색을 종료하는 조건은 아래와 같이 2가지이다.
- 더 이상 쏠 화살이 없는 경우
- 모든 과녁에 대한 연산이 끝난 경우
0번 과녁에 대해서는 연산을 하나마나 점수에 차이가 없으므로 0번 과녁에 도달하게 되면 탐색을 종료한다.
1번의 경우 더 이상 쏠 화살이 없이 도중에 중단되었으므로 arrow 배열이 1번 과녁까지 다 생성되지 않았다. 어차피 더 쏠 화살이 없으므로 배열의 길이가 11이 될 수 있도록 나머지를 [0]으로 채워준다.
점수가 같은 경우 낮은 점수를 많이 맞힌 경우를 구하라고 했으므로, arrow 배열의 마지막에 점수의 차이인 score를 추가한다. arrow 배열은 아래와 같게 된다.
[10번 과녁, 9번 과녁, .... 2번 과녁, 1번 과녁, 점수]
점수가 1순위 비교 대상이고 그 이후로 낮은 과녁 순서대로 차례대로 많은 것부터 비교하면 되므로 배열을 역으로 해서 더 큰 배열이 정답이 되도록 한다.
def compare(a, b):
if a[::-1] > b[::-1]:
return a
return b
def solution(n, info):
def dfs(i, n, score, arrow): # i: 현재 쏜 과녁 번호, n: 남은 화살 횟수, score: 점수 차이, arrow: 쏜 화살 개수
nonlocal ans
if n < 0:
return
# 더 이상 쏠 과녁이 없거나, 쏠 기회가 없는 경우 중단
if i == 10 or n == 0:
# 더 이상 쏠 기회가 없어서 쏘다가 중단된 경우 뒤에 추가 0 붙이기
arrow += [0] * (10-i)
# 남은 횟수가 있는 경우 0번 과녁에 전부 쏴야 한다.
# 그래야 같은 점수일 때 낮은 과녁의 점수가 많아지기 때문이다.
arrow.extend([n, score])
# 가장 마지막 행에 점수를 추가하고 배열을 거꾸로 돌려서 더 큰 배열을 찾는다
# 점수가 가장 큰 배열, 점수가 같다면 낮은 점수가 많은 배열에 저장될 수 있다.
ans = compare(arrow[:], ans)
return
if info[i]:
dfs(i+1, n-info[i]-1, score+2*(10-i), arrow+[info[i]+1])
else:
dfs(i+1, n-1, score+10-i, arrow+[1])
dfs(i+1, n, score, arrow+[0])
ans, tmp, score = [-1]*12, [], -sum(10-i for i in range(11) if info[i])
dfs(0, n, score, [])
if ans[-1] <= 0:
return [-1]
return ans[:-1]
