정현우 / 4기 3주차 / 3문제

[cookingTorch]

문제명 : 망가진 계산기

시간 복잡도 : O(min(8^P, 10^D)) , 공간 복잡도 : O(P)

1. 풀이 과정

- 68 ms
- DFS
- DFS(연산 횟수, 이전에 곱한 값, 계산 결과)
- 이전에 곱한 수 이하의 수들을 곱해보면서 DFS
- 자릿수 초과 시 return
- 연산 횟수 도달 시 최대값 갱신 후 return

---

문제명 : 군대탈출하기

시간 복잡도 : O(NMlogK) , 공간 복잡도 : O(NM)

1. 풀이 과정

- 132 ms
- 이분 탐색 + DFS
- map 1 차원 변환
- 한 줄은 점프 가능하므로 사방에 벽 두 줄 세우기
- 탈출 가능한 최소 레벨 -> lowerBound
- 이분 탐색 해당 레벨로 탈출 가능한지 검증
- 점프 하지 않았고 레벨 제한에 걸리면 점프해서 탐색
- 이미 점프 했거나 레벨 제한에 걸리지 않으면 다음 칸 탐색
- DFS로 목적지에 도달할 때까지 확인

---

문제명 : 호텔

시간 복잡도 : O(NC) , 공간 복잡도 : O(C)

1. 풀이 과정

- 64 ms
- Knapsack
- dp[i] = i 명의 고객을 늘리기 위한 최소 비용
- 현재 정보의 고객 이하 -> 현재 정보의 비용으로 가능
- 현재 정보의 고객 초과
- -> dp[i]는 (dp[i - 고객] + 비용)과 비교하여 작은 쪽으로 갱신

---