[Python] BOJ(백준) 18234번 - 당근 훔쳐 먹기

링크

https://www.acmicpc.net/problem/18234

난이도(solved.ac 참고)

골드4

풀이

여기서 느낀 건, 시간 복잡도의 중요성이었다.

풀이(시간초과)

기존에 내가 풀었던, 시간 초과한 코드를 보면 min과 remove를 같이 썼다. 사실 min 하나만 들어가더라도 이미 이중 반복문과 다를 바가 없었는데, 예제는 다 맞아서 제출했더니 하나도 진행을 하지 못하고 오류가 났다. 다시 곰곰이 생각을 해보니까, t에 대한 for문을 전개할 게 아니라 n에 대한 for문을 전개해야 시간복잡도 선에서 발생하는 문제를 해결할 수 있을 것이라는 생각이 들었다.

 

n(날짜)에 대해서 for문을 전개하려면.. for문 내부에서 가장 나중에 먹을 당근에 투여된 영양제의 횟수를 한번에 구해야했다. 이것을 어떻게 구할지 생각을 해봤는데, 영양제 값을 기준으로 나열한 w_list에 대해서 (영양제의 정도(t) - 날짜(n) + i)를 더해주면 되었다. t-n일 까지는 당근을 먹지 않다가 t-n+1번째 날부터 하나씩 먹어주면 된다.

 

결국 모든 당근을 먹게 되므로 w_list에 대한 반복문을 작성할 때 당근의 초기값은 바로바로 더해줬고, 영양제로 인해 증가되는 값만 마지막 반복문에 따로 넣어서 구했다.