gaelim   2년 전

bottom-up과 up-bottom이 같다고 생각하기에 ,,,

한번 메모이제이션을 써보았습니다.

제가 제대로 메모이 제이션을 썼는지 의문입니다.... 코드는 짧아서 읽으실때 괜찮겠습니다만...

뭔가 작은 테스트케이스는 잘 맞는거같습니다.

 문제는 시간초과입니다. 이런 문제는 구현을 3중 for문으로 해야할까요?

아니면 이정도도 그럭저럭 괜찮은 다이내믹프로그래밍을 했다고할 수있을까요?

 아니면 완전 틀렸나요? 시간초과가 난거보니까 제가 메모이제이션도 제대로 안한거같기도하고 ㅠ.ㅠ

gaelim   2년 전

g허... dfs 함수 안에 쓸모없는 명제가 있는가봐요.

몇개 지우니까 통과되네요... 하 어렵다 ...... 특히 (l==r) return d[l][r]=0 이나 (l==r) return 0 과 연산속도가 다른가요... 허허 ... ㅠ.ㅠ...? 

gaelim   2년 전

@doju long long data type 인 경우 LL 자를 붙여줘야 비트쉬프트가 사용가능한것을 뜻하신거죠??


doju   2년 전

1 << 50int type이고, 1LL << 50long long type입니다. 그리고 left shift operator는 결과값이 자료형이 표현 가능한 범위를 넘어갈 때 undefined behavior를 일으킵니다. 즉 환경마다, 계산할 때마다 값이 달라질 수도 있고 프로그램이 꺼질 수도 있고 컴퓨터가 로봇 혁명을 일으킬 수도 있습니다.
https://ideone.com/SwCKzR

로컬에서는 작은 테스트 케이스가 잘 나온다고 하셨으니 적당히 큰 어떤 값이 나온 모양이지만, BOJ에서는 운 나쁘게 0이 나오는 바람에 시간 초과가 발생한 것입니다.

gaelim   2년 전

@doju 와우 상세하게 설명해주셔서 감사합니다. 그것이 문제 였었네요 감사합니다 와우

gaelim   2년 전

혼자 생각해서 결론내렸다면 완전 이상한 개념이 생길뻔했군요.... 감사합니다

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