dudgh9661   8달 전

시간 초과가 뜨네여..

더 줄일 방법이 생각이 안나 여쭤봅니다!

circlezer0   8달 전

풀어봤는데

그냥 inputdata가 0이 될 때 까지 inputdata보다 작거나 같은 피보나치 수열의 수를 빼면 됩니다.

dp를 이용할 이유가 없는 것 같네요.

dudgh9661   8달 전

풀어봤다는게 문제를 풀어보셨다는건가요 아니면 제 코드로 풀어보셨다는건가요???

circlezer0   8달 전

문제를 풀어봤다는 뜻입니다.

dudgh9661   8달 전

감사합니다

dudgh9661   8달 전

그런데 inputdata가 0이 될 때까지 빼는 과정이 제가 위에 적은 DFS와 비슷한 로직 아닌가요!?

sait2000   8달 전

매번 그리디하게 뺄 수 있는 가장 큰 수를 빼야 합니다.

circlezer0   8달 전

위의 로직은 N을 만들 수 있는 모든 경우의 수를 만들어보고 그 중에서 가장 길이가 짧은 수열을 찾는 로직 같은데,

그 과정에서 시간초과가 나는 것 같네요.

피보나치 수열을 큰 수부터 작은 수로 N과 비교하면서 만든 수열이 '무조건' 가장 짧은 수열이므로

dp를 통해서 모든 결과값을 비교할 필요가 없을 것 같아요.

dudgh9661   8달 전

답변해주셔서 감사합니다~~

댓글을 작성하려면 로그인해야 합니다.