13164번 - 행복 유치원
dp문제처럼 보여 dp로 접근했습니다. 대체 왜 유치원에 30만명이나 있는지는 모르겠지만 n과k의 범위가 너무 커서 dp를 적용하면 메모리 초과가 뜨고 그냥 풀면 (당연히) 시간 초과가 뜹니다. 어떤 알고리즘을 사용해야 풀 수 있나요?
dp로도 풀 수 있겠지만 n과 k의 제한이 너무 크기 때문에 다른 접근방법이 필요합니다.
잘 상각해보면 항상 최선의 선택이 존재 한다는 것을 알 수 있습니다.
감사합니다. 다시 접근해서 풀어봐야겠네요.
댓글을 작성하려면 로그인해야 합니다.
mystika 7년 전
dp문제처럼 보여 dp로 접근했습니다. 대체 왜 유치원에 30만명이나 있는지는 모르겠지만 n과k의 범위가 너무 커서 dp를 적용하면 메모리 초과가 뜨고 그냥 풀면 (당연히) 시간 초과가 뜹니다. 어떤 알고리즘을 사용해야 풀 수 있나요?