TURNOFFTHELIGHTS 문제 질문드립니다. rapguy 안녕하세요. [[problem:TURNOFFTHELIGHTS ]] 문제가 동적계획법으로 되어 있는데, 동적계획법을 어떤식으로 적용해야 할지 도저히 감이 안잡혀 문의드립니다. 제한시간도 20초로 되어 있고 푸신분들도 몇분 안되는 것으로 보아..난감하네요. https://algospot.com/judge/submission/detail/232769 와 같이 풀게 되면 5*8 배열정도까지만 계산이 되고.. 그 이상의 크기는 절대 해결이 안되더라구요. 동적계획법을 적용할수있도록 힌트 부탁드립니다. 10년 전
1개의 댓글이 있습니다. Being 일단 1차원 문제였다면 쉽게 풀었겠죠? 2차원 문제가 되었으니, 한 행씩 고려한다고 하면 각 열을 어떻게 덮었는지를 잘 가지고 있으면 됩니다. 힌트를 드리자면 2^N과 연관이 있습니다. 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
rapguy
안녕하세요.
[[problem:TURNOFFTHELIGHTS ]] 문제가 동적계획법으로 되어 있는데,
동적계획법을 어떤식으로 적용해야 할지 도저히 감이 안잡혀 문의드립니다.
제한시간도 20초로 되어 있고 푸신분들도 몇분 안되는 것으로 보아..난감하네요.
https://algospot.com/judge/submission/detail/232769
와 같이 풀게 되면
5*8 배열정도까지만 계산이 되고.. 그 이상의 크기는 절대 해결이 안되더라구요.
동적계획법을 적용할수있도록 힌트 부탁드립니다.
10년 전