[구현, DP?] 풍선 터뜨리기 (Lv.3)
걸린 시간
70분
접근 방식
처음에는 DP 배열에 모든 최대가 될 수 있는 값과 최솟값도 저장해서 풀어보려고 했으나
a 배열의 길이가 1,000,000 이하이기에 시간복잡도, 공간복잡도를 다 어길 것 같았다.
먼저 찬스를 안쓰는 조건을 먼저 생각해보자
n번째 수를 5라고 잡아두고,
1~n-1의 최솟값과 n+1~l의 최솟값이 있을 때
- 1 5 6 이면 살아남고 (찬스 씀)
- 1 5 4 이면 살아남지 못하고
- 6 5 1 이면 살아남고 (찬스 씀)
- 6 5 7 이면 살아남음 (찬스 안 씀)
즉 찬스를 안썼을 때 기준(n)이 찬스를 쓰거나 안쓰는 경우에 살아남는 경우는 "양쪽 보다 큰 경우가 아닌 경우"
그럼 다음으로 생각해야 될 경우의 수가 찬스를 이미 써서 못 쓰는 경우인데
위 경우에서 찬스를 써서 살아남은 경우가 1 5 6, 6 5 1 이다.
여기서 기억할 것은 찬스를 쓰면 그쪽 범위의 숫자는 무조건 커진다.
- 1+ 5 6 인 경우에 찬스가 없다면?
2 5 6 인데 찬스가 없다 -> 못살아남음 근데 이건 찬스를 안쓰면 살아남으므로 패스
7 5 6 인데 찬스가 없다 -> 살아남음 - 1 5 6+ 인 경우에 찬스가 없다면? -> 못살아남음 근데 이건 찬스를 안쓰면 살아남음
결국 뭐가 됐든 최솟값 기준 1 5 6 (또는 6 5 1) 형태라면 살아남는다.
결론적으로 min(a[:n]) > a[n] or min(a[n+1:]) > a[n] 이면 answer에 +1 해주면 된다.
단, a 배열이 1,000,000으로 길어서 단순 슬라이싱을 계속하면 시간초과가 뜨므로 미리 계산해둘 필요가 있다.
정답 코드
def solution(a):
l = len(a)
if l < 2:
return 1
answer = 2
# 0부터 i까지의 최솟값
start = [0 for _ in range(l)]
start[0] = a[0]
# i부터 l-1까지의 최솟값
end = [0 for _ in range(l)]
end[l-1] = a[-1]
for n in range(1, l):
start[n] = min(start[n-1], a[n])
end[l-n-1] = min(end[l-n], a[l-n-1])
for n in range(1, l-1):
if start[n-1] > a[n] or end[n+1] > a[n]:
answer += 1
return answer배운점
DP 문제는 풀다보면 반례가 나올만한 복잡한 경우의 수는 배제해도 되는 경우가 많은 것 같다.
단 그 반례가 나오지 않음을 증명하려고 고민하다보면 시간이 30분은 훌쩍 넘어버리는 것이 문제인 것 같다.
[구현] 쿠키 구입 (Lv.4)
걸린 시간
40분
접근 방식
부분 합을 미리 다 구하는 것은 4,000,000번 계산이라 충분하다.
두 바구니 배열이 붙어있음을 이용해 k라는 기준을 0부터 올려가며 k에서 천천히 양쪽으로 확장시켜 숫자가 같으면 저장하는 방식으로 풀면 된다.
정답 코드
def solution(cookie):
answer = -1
l = len(cookie)
arr = [[0 for _ in range(l)] for _ in range(l)]
for n in range(l):
arr[n][n] = cookie[n]
for k in range(1, l):
for i in range(l-k):
arr[i][i+k] = arr[i+k][i+k] + arr[i][i+k-1]
print(arr)
for k in range(l-1):
# 첫째의 끝 번호를 k로 둔다. 둘째는 첫 번호를 k+1로 둔다.
## 첫째의 범위 증가 인덱스는 i, 둘째의 범위 증가 인덱스는 j다.
## arr[k-i][k]와 arr[k+1][k+1+j]를 비교하면서 i 또는 j를 증가시킨다.
# 만약 서로 같으면 answer에 저장한다.
# k-i가 0보다 작아지거나 k+1+j가 l 이상이 되면 끝낸다.
i = 0
j = 0
while True:
if k-i < 0 or k+1+j > l-1:
break
# 둘째가 더 많으면 i 증가
if arr[k-i][k] < arr[k+1][k+1+j]:
i += 1
# 첫째가 더 많으면 j 증가
elif arr[k-i][k] > arr[k+1][k+1+j]:
j += 1
# 같으면 저장
else:
answer = max(answer, arr[k-i][k])
i += 1
return answer if answer != -1 else 0배운점
두 바구니 배열이 인접하다는 것을 모르고 처음에 count와 index를 활용해서 풀어보려고 했지만 너무 복잡해져서 힌트를 보게 되었다.
위 방법처럼 k를 다 돌려보면서 조사하는 것은 cookie 배열이 2,000까지가 최대라 가능했던 방법인 것 같다.
