[100][200000] dp가 맞는 풀이가 아닐까 싶은데

tc가 많다보니 dp를 초기화하다가 시간초과가 납니다

아니면 이 풀이가 정해가 아닌건지.. 물론 토글링이 있긴하겠지만 ㅠㅠ

noeffserv   8달 전

배열 [2][200000] 로 풀수도 있구요. [200000] 로도 풀수 있습니다.

noeffserv   8달 전

근데 사실 이 문제 200000*100*100(테케수) 풀이로도 통과하는게 좀 이상하긴 하네요. 시간 초과 걸릴텐데..;

그런가요... 토글링 (%2) 을 사용하지 않고 저렇게 풀 수 있는건가요?

noeffserv   8달 전

네 역으로 돌리면 가능합니다.

예를 들어 0 부터 돌리는게 아니라 20만부터 0까지 돌리면 가능해요

음.. 그렇군요 생각해보겠습니다. 답변감사합니다!

antiwar   8달 전

소스보니 재귀로 하셨던데 for로 하고 최적화 좀 하면 맞으실듯 하네요

그냥 의도가 for문 두개는 어쩔수없고, 적당히 최적화 해라 이거같은데요

java로는 입출력 땜에 시간초과가 많이 났었어요;;

ㅠㅠ 제가 DP를 반복문으로 푸는걸 거의 못해서...ㅋㅋㅋㅋㅋㅋㅋㅋ

공부해야된다고 생각은 하지만 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

일단 한번 20만으로도 된다고 하시는걸 생각해봐야겠어요..

감사합니다 ㅎㅎ

antiwar   8달 전

아... 위에분이 말씀주신건 반복문으로 구현할때 말씀주신거 같아요
재귀로는 일차원에 캐시하는건 위 문제는 1개씩 있는 동전문제랑 유사해서 안될거 같아보이네요
https://www.acmicpc.net/problem/2294 -> 해보진 않았는데요 이런건 재귀로도 1차원에 캐시 될거같습니다.

( 근데 시간복잡도는 그래도 그대로일거 같은; )

noeffserv   8달 전

antiwar 네 반복문으로 구현할때 맞아요 

음.. 제가 말한 방식으로.. 재귀로는 어떻게 구현해야할지 아직 감은 안잡히네요

재귀로는 아마 안될것같아요...ㅋㅋㅋ

이게 타임아웃나는게 케이스마다 dp배열 초기화를 하다 나버리다보니 ㅋㅋㅋ

antiwar   8달 전

orange4glace 테스트 케이스가 java로도 잘 짜면 1초내로 나올수 있을정도로 빡세진 않은거 같아서..

여기는 능력자분들이 많으니 ㅎ 재귀로도 최적화 잘해서 가능할수도 있을거 같은데요?( 일차원 캐시는 안될거 같지만..) 
큐브러버님 한번 소환해 보세요; 음 만일 저한테 큐브러버님이 최적화 해서 재귀로 패스할수 있냐 없냐에 
신사임당 한장을 걸라고 하면 있다에 한번 걸고 싶네요
( 저번에 java최적화 하시는거 한번 봤는데 대단하시더군요 )

ㅜㅜ 말씀보고 나름대로 해봤는데 제 미천한 실력으론 안되네요.. 

cubelover  님 도와줘요!.. 라고하면 오시나?

antiwar   8달 전

일단 chatterboyyukariko 님도 재귀로 맞으셨네요 ㅎㄷㄷ 갓님들 ㅋ 답주실듯

뭔가 재귀함수 첨에 if(m * 2 >= M) return 0; 이거 넣어서 좀 줄이면 될수도 있을거 같은데;

큰 차이점은 잘 모르겠네요

헐 미쳤다 진짜 엄청 감사해요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

저는 남은 용량을 체크해서 남은 용량으로 할당량을 충당 할 수 있는지만 보는걸 생각했네요...

이미 용량을 충당했으면 0을 리턴하는 걸 아예 생각을 안한... 또 하나 배워가네요 감사합니다 ㅎㅎ

최적화를 두번 해주니 무려 400ms까지 떨어지네요..

최적화를 dp에서 저는 괄시하고 있었는데.. 정말 중요한거네요 정말 배워갑니다 ㅎㅎ

antiwar   8달 전

ㅎ 도움되었다니 다행입니다.

저도 추가로 재귀로 내보았는데 쉽지 않았네요 ㅠ

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