첫 문제접근
나올 수 있는 점수를 모두 생각했다. 이 문제의 경우에는 1~20 그리고 2의 배수들, 3의 배수들, 50이 있다.
해당 점수들로 target을 만들 수 있는 조합은 굉장히 많다.
거기서 가장 적은 수로 조합하고, 조합한 화살의 개수가 같다면 Single이나 50점을 많이 쓴 경우를 출력한다.
만약 이마저도 같다면, 먼저 던진 선수가 승리한다는데, 이 조건은 필요 없다.
어차피 우리가 구해야 하는 것은 가장 적은 개수의 조합으로 target을 완성했을 때 single과 50점을 몇 개나 맞췄는지를 구하는 것이다.
시간복잡도
- 1 ≤ target ≤ 100,000
최대 Nlog(N)의 시간복잡도로 접근해야 한다.
해당 문제는 target을 달성해도 또 조건이 있기 때문에 greedy로는 풀 수 없다.
최선의 경우의 수가 target이 변할 때마다 최적의 조건으로 변하기 때문에 DP를 생각해 볼 수 있다.
그러나 나는 여기까지 밖에 생각을 못했다. 구현하기가 너무나 어려웠음.
다른 풀이를 참고했다.
문제 풀이
- DP를 이용해서 역순으로 target을 줄여가며 0이 될 때까지 최적의 경우를 찾아간다.
- 50점이 가능한 경우, Single이 가능한 경우, 두 배, 세 배 점수를 맞춰서 가능한 경우를 나눈다.
2-1. 50점과 Single을 최대한 써야 하기 때문에 if를 앞단에 배치한다. - 50점 또는 Single이 더 많은 경우 DP값을 갱신한다.
아래 주석으로 설명하겠다.
def solution(target):
answer = []
# 이렇게 쓴 이유는 아래 설명
dp = [[target-i, target-i] for i in range(target+1)]
# 목표 점수에서 0점까지 역순으로 탐색
for i in range(target, -1, -1):
# 1점부터 20점까지 점수를 고려
for j in range(20, 0, -1):
# 50점을 쏠 수 있는 경우
if i-50 >= 0:
# 50점을 쐈을 때 화살 개수가 더 적다면 갱신
if dp[i-50][0] > dp[i][0]+1:
dp[i-50] = [dp[i][0]+1, dp[i][1]+1]
# 더 많이 쏜 불 또는 싱글 수로 갱신
elif dp[i-50][0] == dp[i][0]+1 and dp[i-50][1] < dp[i][1]+1:
dp[i-50] = [dp[i][0]+1, dp[i][1]+1]
# 싱글을 쏠 수 있는 경우
if i-j >= 0:
# 더 적은 화살 수로 갱신
if dp[i-j][0] > dp[i][0]+1:
dp[i-j] = [dp[i][0]+1, dp[i][1]+1]
# 더 많이 쏜 불 또는 싱글 수로 갱신
elif dp[i-j][0] == dp[i][0]+1 and dp[i-j][1] < dp[i][1]+1:
dp[i-j] = [dp[i][0]+1, dp[i][1]+1]
else:
# 남은 점수가 단일 점수보다 작으면 더 이상 진행하지 않음
break
# 더블 을 쏠 수 있는 경우
if i-2*j >= 0:
# 더 적게 쏴서 도달할 수 있을 때
if dp[i-2*j][0] > dp[i][0]+1:
dp[i-2*j] = [dp[i][0]+1, dp[i][1]]
# 같은 수를 쐇지만, 불 또는 싱글을 더 많이 맞출때
elif dp[i-2*j][0] == dp[i][0]+1 and dp[i-2*j][1] < dp[i][1]:
dp[i-2*j] = [dp[i][0]+1, dp[i][1]]
# 트리플 을 쏠 수 있는 경우
if i-3*j >= 0:
# 더 적게 쏴서 도달할 수 있을 때
if dp[i-3*j][0] > dp[i][0]+1:
dp[i-3*j] = [dp[i][0]+1, dp[i][1]]
# 같은 수를 쐇지만, 불 또는 싱글을 더 많이 맞출때
elif dp[i-3*j][0] == dp[i][0]+1 and dp[i-3*j][1] < dp[i][1]:
dp[i-3*j] = [dp[i][0]+1, dp[i][1]]
# 목표 점수에 도달하기 위한 최소 화살 수와 최대 불 또는 싱글 수 반환
return dp[0]
코드해석
본인은 저 코드만 보고 이해하기 어려웠다.. 좀 더 해석을 덧붙이겠다.
dp = [[target-i, target-i] for i in range(target+1)]
이렇게 작성한 이유는 DP를 뒤에서부터 진행하기 때문이다.
dp[i]의 인덱스 i는 현재 점수를 나타낸다.
예를 들어
dp[100]은 목표 점수 100에 도달하는 경우를 나타내고,
dp[50]은 목표 점수 50에 도달하는 경우를 나타낸다.
target이 100이라면
# dp[100] = [0, 0] # 100점에 도달하기 위한 초기값 (화살 0개, 싱글 0개)
# dp[99] = [1, 1] # 99점에 도달하기 위한 초기값 (화살 1개, 싱글 1개)
# dp[98] = [2, 2] # 98점에 도달하기 위한 초기값 (화살 2개, 싱글 2개)자 여기까지 이해됐다면, 아래 코드까지만 해석해보겠다. 아래가 이해된다면 모든 게 끝
for i in range(target, -1, -1):
# 1점부터 20점까지 점수를 고려
for j in range(20, 0, -1):
# 50점을 쏠 수 있는 경우
if i-50 >= 0:
# 50점을 쐈을 때 화살 개수가 더 적다면 갱신
if dp[i-50][0] > dp[i][0]+1:
dp[i-50] = [dp[i][0]+1, dp[i][1]+1]
# 더 많이 쏜 불 또는 싱글 수로 갱신
elif dp[i-50][0] == dp[i][0]+1 and dp[i-50][1] < dp[i][1]+1:
dp[i-50] = [dp[i][0]+1, dp[i][1]+1]여기서
if dp[i-50][0] > dp[i][0]+1:
dp[i-50] = [dp[i][0]+1, dp[i][1]+1]이부분이 이해가 잘 안됐다. 여기서 주의해야 할 점은 dp[i-50][0]이 50점을 쐈을 때 화살의 개수가 아니다. dp[i][0]+1이 50점을 쐈을 때 화살의 개수이다.
i가 100일 때를 생각해보자
dp[50][0] > dp[100][0]+1 을 비교하게 된다.
처음 dp[50][0] = 50으로 세팅되었고, d[100][0] = 0이다.
그러니 50점을 맞췄다고 가정했을 때 화살의 개수는 d[100][0] + 1 이 된다.
이것은 1이고 dp[50][0]보다 작으니 dp[i-50] = [dp[i][0]+1, dp[i][1]+1] 처럼 갱신한다.
아래 코드들도 그런 식이다. .
후기
솔직히 처음에 코드를 보고 이해가 어려웠다.
어떻게든 이해해보고 싶었는데, 설명할 수 있다면 이해했다고 할 수 있지 않을까 싶어 작성했다. 한 명이라도 도움이 되었다면 좋겠다.
