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

[cookingTorch]

문제명 : 파일 합치기

시간 복잡도 : O(N^2) , 공간 복잡도 : O(N^2)

1. 풀이 과정

- 136 ms
- 크누스 최적화
- dp[i][j] : i ~ j - 1 까지 합치는데 필요한 최소비용
- sum[i][j] : i ~ j - 1 까지 소설 장 수 구간 합
- i <= mid <= j 일 때,
-   dp[i][j] = min(dp[i][mid] + dp[mid][j]) + sum[i][j]
- a <= b <= c <= d 일 때,
-   sum[a][c] + sum[b][d] <= sum[a][d] + sum[b][c] 이고,
-   sum[b][c] <= sum[a][d]
- sum[i][j]가 사각 부등식과 단조성을 만족하므로 크누스 최적화
- mids[i][j] : dp[i][j]를 최소로 만드는 mid
- mids[i][j - 1] <= mids[i][j] <= mids[i + 1][j]

---

문제명 : 곡예 비행

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

1. 풀이 과정

- 468 ms
- DP
- up[i][j] : (i, j)에 도착하는 상승비행 최대 점수
- up[i][j] = max(up[i + 1][j], up[i][j - 1]) + map[i][j]
- down[i][j] : (i, j)부터 시작하는 하강비행 최대 점수
- down[i][j] = max(down[i + 1][j], down[i][j + 1]) + map[i][j]
- up[i][j] + down[i][j] 최대값 출력

---