More actions
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
* DP 문제이다. | * DP 문제이다. | ||
* 업 시퀀스 문제라 봐야될 것 같다. | * 업 시퀀스 문제라 봐야될 것 같다. | ||
* 각각의 돌마다 거리를 비교하면서 하면 될 줄 알았으나.. '''시간초과가 남''' | * 각각의 돌마다 거리를 비교하면서 하면 될 줄 알았으나.. '''시간초과가 남''' (N크기 최대 백만, 시간복잡도-O(N^2)) | ||
* 따라서 거리 비교를 최소화 하려고 변수를 하나 도입, 뒤에서 쫓아가면서 거리를 확인 | * 따라서 거리 비교를 최소화 하려고 변수를 하나 도입, 뒤에서 쫓아가면서 거리를 확인 | ||
Revision as of 07:24, 8 July 2016
오늘의 문제
참가자
코드
아이디어
박인서
- DP 문제이다.
- 업 시퀀스 문제라 봐야될 것 같다.
- 각각의 돌마다 거리를 비교하면서 하면 될 줄 알았으나.. 시간초과가 남 (N크기 최대 백만, 시간복잡도-O(N^2))
- 따라서 거리 비교를 최소화 하려고 변수를 하나 도입, 뒤에서 쫓아가면서 거리를 확인