백준 2616 소형기관차 해설/풀이 (파이썬), 골드4 다이나믹 프로그래밍 문제

풀이 코드만 궁금한 분은 깃허브링크 눌러주세요..!!

GitHub - Rhyankwon/algorithms

 

문제 해설

 

 

간단히, 숫자들이 입력된 리스트가 있는데 거기에서 s칸씩 연결된 부분리스트들을 3개 만들어야 한다. 이 때 3개의 부분리스트들은 서로 겹치면 안되고, 이 때 부분리스트들의 합이 최대가 되는 3쌍의 부분리스트들을 찾아서 그 합을 리턴하면 된다.  

 

 

문제 해결 논리

 

1. 우선 전체 n개의 칸 중 s칸씩만 합할 수 있으므로, 입력된 숫자리스트에서 s칸만큼의 부분합을 저장하는 리스트를 만들고 s부터~n까지 각각 부분합을 저장해둔다. s-1까지는 s갯수를 채우지 못하니까 0으로 저장해둔다. 마지막 칸에는 n-s부터 n째칸까지의 합이 들어간다. 이 리스트를 부분합리스트 라고 하자.

2. 3개의 행, n개의 열로 이루어진 dp리스트를 선언한다.

3. 맨 첫째 행 부터 값을 넣을 건데, k째 열의 값은 k-1째 열의 값과 부분합리스트의 k째 열의 값 중 최대값이다. 이게 무슨 말이냐면, 부분합리스트를 순회할 때 이전값과 현재값을 비교해서 더 큰값을 dp[0][k]에 넣는다는 뜻이다.

4. 두번째 세번째 행의 k째 열의 값은, (이전 행의 k-s째 열의 값 + 부분합리스트[k째 값])과 (현재 행의 k-1째 열의 값)을 비교한 최댓값이다. 다시 말하면, 이전 행의 값에 새로운 부분합(매 칸은 s만큼의 길이가 소요되므로 이전 행의 k-s째 열의 값을 사용해야 한다)을 추가하는 것과 직전값을 비교한 최댓값이 현재값이 된다는 뜻이다.

 

 

최대한 쉽게 설명해보려고 했는데 역시 dp는 그림이 없으면 설명하기가 어렵다. 개인적으로는 잘 풀었다고 생각했는데 순위는 생각보다 낮더라,,ㅋㅋㅋㅋ 범위 설정을 잘 하면 필요없는 연산을 줄이는게 명확하게 나오는 문제라서 이것저것 시도해봤는데 아주 살짝 속도가 올라갔을뿐이라 그냥 만족하기로 했다. 

 

 

 

------------------------------------잡담(속도개선)-------------------------------------

문제를 풀고나서 다른 사람들의 풀이 속도도 봤는데 1등부터 거의 뒷쪽 등수까지 사실 속도차이가 크게 나는수준은 아니였다. 근데 맨 뒷쪽에 2000ms 이렇게 속도가 나오는 사람들도 있어서, 아마 속도가 그렇게 나오는 사람들은 부분합리스트를 만드는 부분에서 비효율적으로 풀지않았나 싶다. 나는 처음에 풀때 그 부분을 무조건 sum(부분리스트)로 하면 비효율적일 것 같아서 sum(이전 부분리스트 - 사라지는 값 + 새로운 값)이렇게 풀었다. 문제를 다 풀고나서 만약 처음 생각했던 방식대로 풀면 어떻게 될까 싶어서 그렇게 해봤는데 2000 ms정도가 나오더라. 당연한 말이지만 50000까지 갯수가 들어갈 수 있는데 거기에서 만약 s(부분합을 이루는 칸 수)갯수가 5000 이런식이면 5000을 45000번만큼 해야 부분합리스트가 나온다. 당연히 이 부분이 dp부분보다 속도를 많이 잡아먹을 수 밖에 없으니까 고치면 속도개선에 도움이 된다.