[백준] 11066번: 파일 합치기 - Python
2023. 2. 23. 22:29ㆍ백준 & 프로그래머스
문제보기
https://www.acmicpc.net/problem/11066
11066번: 파일 합치기
소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본
www.acmicpc.net
풀이 및 코드
해당 문제는 dp를 이용해 푸는 문제로 solved.ac.기준 골드 3에 랭크되어 있다. 요즘따라 dp 문제를 유독 많이 푸는 것 같다ㅎ
핵심 점화식은 다음과 같다.
for i in range(s, e):
dp[s][e] = min(dp[s][e], dp[s][i] + dp[i+1][e])
dp[s][e] += sum(arr[s, e+1])
dp에는 s부터 e까지 합치는 데 필요한 최소비용이 저장되어 있다. 즉 필자는 i를 기준으로 (s,i), (i+1)으로 구간을 나누어 최소비용을 구한뒤 그 합이 작은 값을 찾고자 했다.
'백준 & 프로그래머스' 카테고리의 다른 글
| [백준] 3758번 KCPC - python (0) | 2023.04.07 |
|---|---|
| [프로그래머스] 롤케이크 자르기 - python (0) | 2023.04.01 |
| [백준] 2228번: 구간 나누기 - python (0) | 2023.02.22 |
| [백준] 9376번: 탈옥 - 파이썬 (1) | 2023.02.05 |
| [백준] 7579번: 앱 - 파이썬 (0) | 2023.02.01 |