[BOJ_10025] 게으른 백곰

 

📌 문제 링크: https://www.acmicpc.net/problem/10025

10025번: 게으른 백곰

 

❌ 내 풀이(Failure) :

sum() 함수의 시간복잡도를 생각하지 못한 풀이

 

✅ 내 풀이(Success) :

 

🧐 Review:

 입력 값의 크기의 최댓값이 꽤 크기 때문에 시간 복잡도를 O(n)으로 줄이지 않는다면, 무조건 '시간 초과'로 틀릴 수밖에 없다. 그래서 for 반복문 하나로 코드를 작성했지만... 이상하게도 '시간 초과'로 틀리게 되었다. 작성한 코드에서 어떤 부분이 문제가 되는지 하나씩 변경해보면서 테스트를 해보다가 얼음의 양을 구하는 sum() 함수가 O(n)의 시간 복잡도를 가진다는 것을 알게 되었다. 그래서 for 반복문의 시간 복잡도 O(n)과 sum() 함수의 시간 복잡도 O(n)으로 전체 시간 복잡도가 O(n^2)이 되어서 문제를 틀릴 수밖에 없었다.

 이 부분을 해결하기 위해 슬라이딩 윈도우 알고리즘을 적용해서 초기 값으로 앨버트가 닿을 수 거리를 계산해서 초기 구간의 합을 구했고, 윈도우를 한 칸씩 옮길 때마다 더하거나 빼야 되는 부분을 for 반복문을 이용해서 계산했다. 그리고 윈도우가 옮겨질 때마다 answer과 window의 얼음의 양을 비교해서 최댓값을 answer에 업데이트하도록 코드를 작성했다.

 

🚩 Idea:

 - MAX를 1,000,001로 설정한 이유 : 얼음 양동이의 좌표 값이 0을 포함하고 최대 1,000,000까지의 범위를 갖기 때문에