목록knuth_optimization (1)

코딩하는 Fug

11066 파일 합치기

https://www.acmicpc.net/problem/11066 #dp #knuth optimization 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net #파이썬의 한계를 볼 수 있었던 문제 #단순 dp로 풀라면 풀 수 있지만 괴랄한 시간이 나온다. #크누스 알고리즘이 필요하다 #조건은 1. 단조성 2. 사각방정식 3. 점화식의 형태 a[i][j]=min(a[i][k]+a[k][j])+c[i][j]일때 가능 #단순히 생각해서 이번 문제에 맞게 되었다고 보면 된다. 그냥 모르고 하면 힘들듯.. #1..
백준풀이-python 2022. 5. 2. 12:25
이전 Prev 1 Next 다음