BOJ 2225를 풀면서 dp - sliding window를 쓸 때 주의할 점!

dp에서 memory를 줄이기 위해 sliding window기법을 썼지만, 틀렸습니다가 나와서 내가 직접 확인해보니 AC코드의 답보다 더 컸고, 입력이 커질수록 그 차이는 더 커졌다. 이 문제의 경우 바로 직전 행의 값들로 현재의 행의 값을 채우기 때문에 sliding window적용하기도 매우 쉽고 잘 적용했는데, 왜 그런걸까... 꽤 오래 고민하다가 직접 출력을 해서 봐야겠다는 생각이 들어 직접 출력해보고 나서야 이유를 깨달았다.

이 문제의 경우, 현재 칸의 값을 구하기 위해서는 직전 행의 값들의 합을 구해야되서, 직전 행의 값들을 현재 칸의 열 범위까지 하나씩 더해준다. 근데, sliding window를 쓰지 않고 했을 경우, d배열을 0으로 초기화한 상태에서 하기 때문에 괜찮은데, sliding window기법을 썼을 경우에는 맨 처음을 제외하고는, 즉 두 번째 부터는 d배열에 값이 들어가있다. 그래서 거기다가 더해주게 되는 것이고 AC코드보다 더 큰 값이 나왔던 것이다.

그래서그 합을 구하는 for문에 들어가기 전에 배열을 0으로 초기화해 주었고, AC를 받았다.

//그리고 이 문제는 2차원 배열에서 sliding window를 쓰는 방법 말고도, 그냥 1차원 배열로 써서 메모리를 줄일 수 있고, 또한 속도도 더 빠르게 하는 방법들이 존재한다.

잊어버릴 때쯤복습, 그리고 복습 또 복습! 결국은 일정 기간을 두고 꾸준한 복습뿐이다!