siosio24   1년 전

재귀함수 돌아가는 원리를 잘몰라서 처음으로 이곳저곳 찾아가면서 종이에 써가면서 낮부터 지금까지 계속 짯는데
입출력 예제 답은 나오는데 제출하니까 타임에러가 뜨네요 ㅠㅠ
입력제한도 350개 던데 이거 고칠수 있는 방법 없을가요?

pichulia   1년 전

일단 저 재귀함수 내부를 원래 모습을 최대한으로 유지한 채 수행 시간이 최소한으로 줄어들도록 고쳐봤습니다.

i번 째 수도관을 선택?했을 때에만 k에 그 수도관을 넣어주고 kkk를 수행.
그 이외의 경우에는 전부 무시하게 하면 논리적 오류 없는 재귀함수가 탄생합니다.

하지만 시간초과는 해결할 수 없겠죠?

예를 들어 P가 350이고 D가 100,000 이라고 칩니다.

1 1 이런게 349개, 99,999 1 이런게 1개 들어온다고 치면
현재의 소스코드는...음...대충 한 10^90년정도? 후에 1이라는 답을 도출하겠네요..
아마 우주가 멸망하기 전까지도 답을 도출하지 못할 것입니다.

그럼 어떻게 하냐고요?


그런 당신에게 마법의 링크를 달아드립니다.

https://www.acmicpc.net/wiki/%EC%95%8C%EA%B3%A0%EB...

물론 이거 하나만으로 해결되는, 그리 간단한 문제는 아니지만...생각은 해보세요ㅋㅋㅋ

siosio24   1년 전

코드는 정말 말끔해졋네요.. 덕분에 재귀돌아가는게 온전히 이해가 갓어요!
여전히 시간초과는 뜨지만 .. 좀더할 의지가 생겻네요 감사합니다

siosio24   1년 전

조금만 더 힌트 주시면 안될까요? 알고리즘 시작한지 얼마 안되서 개념이 많이 부족해 저기서 멀 더 어떻게해야될지 모르겟습니다 벌써 열두시간째네요 ㄷㄷ

재귀호출로는 최적화를 많이 해도 사실상 불가능할 듯합니다. ㅠㅠ

소팅과 DP, 슬라이딩 윈도를 사용해서 해결이 가능합니다.

DP와 슬라이딩 윈도에 대해서는 pichulia님이 올려주신 링크를 포함해 참고자료가 여기저기 많습니다.

찾아보시고 재귀호출을 DP로 바꾸신 후에 구현 중 문제가 되는 부분을 다시 올려주시면 아마 많은 분들이 답변을 달아 주실 거예요

siosio24   1년 전

감사합니다 ! 재귀로 안된다는거 안것만으로도 충분합니다 ㅋㅋㅋ 나중에 뒤에 더 공부하고 다시 이 문제를 풀러와야겟네요 정말감사합니다!!

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