백준 2281번 데스노트 풀이/코드 (파이썬) 꽤 어려운 다이나믹 프로그래밍 문제

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

 

문제 설명ㄱㄱ

간단히 얘기하자면, 열의 갯수만 지정된 어떤 리스트가 있고 각 칸에 *을 넣는데 이 때 주어진 숫자만큼만 이어서 *을 넣을 수 있고 그 이후에는 한칸만 띠고 다시 *을 넣던가 혹은 다음 행으로 넘어가서 다시 *을 넣어야 한다. 이 때 각 행은 오른쪽 끝에 무조건적으로 0칸 혹은 몇개의 칸이 남게 되는데, 각 칸의 제곱의 합이 최소가 되는 경우를 찾아 그 최소값을 반환하는 문제이다. 이 때 마지막 행의 빈칸은 포함하지 않는다.

 

 

문제 해결 논리

 

1. 우선 dp라는 리스트를 선언하는데, 가로=열의 총 갯수, 세로=숫자의 총갯수이다.

2. n번째 숫자에 해당하는 별을 넣을 때에는 n-1번째의 별의 다음 행에 새로 시작할 수 있고, n-1째 별의 마지막에서 한칸 띄고 이어서 넣을 수도 있다.

3. 이 때 같은 칸에 이어서 넣는 경우에는 전체 칸의 갯수 내에 최소한 n번째 숫자만큼 여유공간이 남아있는 경우이다.

4. 따라서 n-1번째 숫자가 k번째에서 끝나는 경우 이 뒷쪽부터 모두 더해온 최소값은

첫째, n번째 숫자가 다음행에 새로 시작하는 경우의 최솟값 + 지금 남은 빈칸 갯수^2,

둘째, n번째 숫자가 같은 행에서 한칸 띄고 새로 시작하는 경우의 최소값

둘 중에 더 작은 값이다. 물론 둘째의 경우는 여유가 되는 경우에만 확인하고, 둘째의 경우가 없는 경우는 무조건 첫째의 값을 따라간다.

 

4-1. 따라서 재귀를 활용하는데, 1번째 값은 2번째 숫자가 1번째 값과 같은 칸에 오는 경우와 다음 행에 넘어가는 경우 중의 최솟값이 된다.

4-2. 뒷쪽부터 계산하는 것처럼 보이는데 사실 매번, 4번의 첫째 룰에 따라, 지금 남은 빈칸 갯수^2를 더해주고있기 때문에 뒷쪽부터 값이 결정되어지긴 하지만 사실 그 또한 매번 앞의 값이 더해진 값일 뿐이다. 말이 이상하니까 이해안되면 스킵해도 될듯..

4-3. 매번 n째 숫자의 k째 열에서의 최솟값을 저장해두고 앞쪽 값을 계산할때 활용한다.

4-4. 맨 마지막 값은 새 행에 들어가든, 이미 있던 행에 들어가든 무조건 0이기 때문에 이 부분을 주의하자.

 

 

처음에 혼자 프린트한 문제를 가지고 30분정도 생각해봤는데 도무지 풀리지가 않아서 이건 다른 사람 풀이를 보고 풀어야겠다고 생각을 했었다. 근데 나중에 컴퓨터 앞에 가서 구글링해봐도 파이썬 풀이가 나오지를 않았다...ㅜㅜ c++풀이는 있었고 c++도 아예 안배웠던건 아니라서 한번 봤는데, 이게 그.. 주어진 숫자마다 k번째 열에서 끝나는 최선의 경우를 저장해두면서 푸는 형식이라는걸 알 수 있었다. 대충 감이 와서 삼십분정도 잡고 풀었는데 도무지 값이 나오지를 않아서 무려 두시간 가까이 헤맸다. 근데 아무리 생각해봐도 내가 논점은 맞게 잡은 것 같아서.. 싹 지우고 다시 처음부터 풀어봤는데 내가 큰 실수를 하나 했었다는걸 알게 됐다. 바로, 4-4에 나온것처럼, dp의 마지막행은 무조건 0이라는 점이다. 마지막 값은 어디에 들어가든 이후 값을 계산하지 않기때문에, 만약 마지막 값과 같은 행의 앞쪽에 다른 값이 있으면 그 값들의 dp행들도 모두 0이라는 점.에서 혼란을 겪었다. 이 부분만 미리 찾았으면 진작 풀었겠지만.. 어쩔수없지머..ㅋㅋㅋㅋ 

 

파이썬 풀이가 별로 없어서 도움이 됐길 바랍니다. 코드는 위에 쓴것처럼 깃허브링크에 있으니까 한번 돌려보실 분들은 돌려보세요!

 

 

---------------------------------------잡담---------------------------------------

 

 

1. 확실히 백준 정답률은 믿으면 안되는 듯 하다. 구글이나 네이버에서 검색해봐도 파이썬 해설이 없어서인지 파이썬은 지금까지 맞춘사람이 해봐야 17명밖에 안되고, 또 정답률도 26%다. 이에 반해 검색하면 나오는 c++풀이는 46%이다. 파이썬도 c++만큼 기본 언어로 공부하는 사람이 많은걸 감안해봤을 때 많은 사람들이 다른사람의 풀이를 바탕으로 풀어보고 제출한다고 가정할 수 있다. 문제가 유명할수록 그 정답률은 믿으면 안되는듯. 나도 두시간까지 헤맸을 때 도저히 못풀겠다 싶어서, c++로 공개된 코드를 검색해서 제출했다. 파이썬 풀이를 보고싶어서. 나도 시간이 더 있었으면 풀긴 했겠지만 c++ 정답률에는 확실히 믿음직하지 않은 데이터를 준 셈이다.

 

2. 재귀는 오류가 나는 경우 recursion을 꼭 수정해주자. 다른사람 풀이를 봐도 역시 내 풀이가 거의 정답에 근접한것같아서 결국 안 보고 풀긴 했지만..? 어.. 이건 다른사람 코드 안 봤으면 헤맸을듯; 런타임 에러가 나는데 불현듯 다른사람이 리컬젼 리밋을 수정해놨던게 기억나서 나도 넘어갈 수 있었다.

 

3. 내가 초반에 헤맸던 이유 중 하나가, dp라고 알고 처음에 풀기 시작했는데 아무리봐도 완전탐색을 해야되서 dfs를 해야할 것 같았다. 근데 에이 아니겠지-라는 마인드로 gg쳐버림. 다른사람 풀이를 보니까 dfs를 했더라..는,, dfs랑 dp를 떼지 않고 생각하는 연습을 해야겠다.

 

3. 풀고 나서 보니까 정말 좋은 문제이다. 적당히 어렵고 적당히재밌다!