[DP] 거스름돈 (Lv.3)
걸린 시간
1시간 초과
접근 방식
그리디는 아니기에 일단 무작정 순수 재귀 탑다운 형식으로 풀어보았다.
45분 정도에 모든 케이스가 맞는 코드는 짰으나 시간 초과가 나고 말았다.
오답 코드
def solution(n, money):
if len(money) == 0 or n == 0:
return 1
if len(money) == 1:
return 1 if n % money[0] == 0 else 0
res = 0
num = money[-1]
for i in range(0, num * ((n // num) + 1), num):
if n - i >= 0:
val = solution(n-i, money[0:-1])
res += val
return res메모이제이션을 써야겠다고 생각했지만 마땅히 방법을 찾지 못해 해설을 보게 되었다.
첫 동전으로 모든 금액(첫 동전 ~ 목표 금액)으로 만들 수 있는 경우의 수를 배열에 저장하고
두번째 동전부터는 첫번째 동전으로 만들수 있는 경우의 수를 가져와 누적해서 저장하는 방식이다.
정답 코드
def solution(n, money):
dp = [0] * (n + 1)
dp[0] = 1
for m in money:
for i in range(m, n + 1):
dp[i] += dp[i - m]
dp[i] %= 1000000007
return dp[n]배운점
정답 코드는 너무나 간단해서 한숨이 나올정도 였다.
구현 난이도보단 dp를 제대로 효율적으로 생각하는 방법을 공부하는 문제였다.
[수학] 최고의 집합 (Lv.3)
걸린 시간
7분 50초
접근 방식
일단 n > s면 [-1]로 두고
거의 대부분의 원소가 중앙값에 맞으면 된다.
n이 5, s가 18이라면 4 4 4 3 3이 될 것이다.
정답 코드
def solution(n, s):
if n > s:
return [-1]
val = s // n
num = s % n
answer = [val for _ in range(n)]
for i in range(n-num, n):
answer[i] += 1
return answer배운점
레벨에 속지말자. 쉬운 문제도 있다.
[그리디] 단속카메라 (Lv.3)
걸린 시간
35분
접근 방식
끝나는 루트가 있을 때 끝나는 지점을 포함하고 있는 모든 루트 제외시키면 된다.
visited를 쓰려고 했지만 거의 다 지워져도 반복문을 불필요하게 반복시킬 것 같아 del 함수를 사용했다.
정답 코드
def solution(routes):
answer = 0
routes.sort(key=lambda x: x[1])
while routes:
answer += 1
del_idx = []
val = routes[0][1]
for i in range(1, len(routes)):
if routes[i][0] <= val <= routes[i][1]:
del_idx.append(i)
del_idx.sort(reverse=True)
for i in del_idx:
del routes[i]
del routes[0]
return answer
print(solution([[-20, 15], [-14, -5], [-18, -13], [-5, -3]]))배운점
del 함수는 O(N)이다. (뒤에 당겨우는 데이터의 값의 양에 따라 선형적으로 증가)
routes.sort(key=lambda x: x[1])유용한 이중 리스트의 정렬방법인데, 리스트 내의 element의 2번째 인덱스를 기준으로 정렬한다는 뜻이다.
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 에서
[[-20,-15], [-18,-13], [-14,-5], [-5,-3]] 가 된다는 소리다.
