안녕하세요.

우선, 이문제는 탑다운으로도 충분히 풀립니다. 저도 [2][3001][3001]캐쉬 선언해서 AC를 받았습니다.

dp함수의 현재상태선언이 잘못된것같습니다.(점화식의 오류) 이런 경우는 간단한 로우데이터를 넣어서는 반례를 찾기 쉽지않습니다.

그리고 문제에서 주어진 순서대로가아니라 idx를 N-1부터 0까지 거꾸로 접근하면 로직의 잘못된점을 찾기가 힘듭니다. 정상적인 흐름이 아니기 때문입니다.

idx를 0부터 접근시키도록 함수를 수정하고, 문제의 로직에따라 천천히 다시 구현하시면 충분히 AC를 받으실 것 같습니다.

그리고 반례를 하나 찾아 첨부해 두겠습니다.

또 밑에 저의 로직을 써놓았으니, 스포일러를 피하고 본인의 힘으로 푸시겠다하시면 여기까지 글을 읽으시고 함수를 수정하시면 됩니다.

// 점화식 스포일러

//

//

기저사례: if(idx==N)return 0

if(sleep할수 없으면) return ret=f(0,cnt,idx+1);

if(자고있으면)return ret=max( f(1,cnt-1,idx+1)+값,f(0,cnt,idx+1) )

else return ret=max( f(1,cnt-1,idx+1),f(0,cnt,idx+1) )

@newdeal
너무 감사드립니다  한번 제 힘으로 꼭 풀어고보고 싶어서 다시한번 꼼꼼히 보고 오겠습니다 답변 너무 감사드려요 ㅠㅠㅠㅠㅠ

@newdeal

https://www.acmicpc.net/source/18159473

도와주신 덕분에 AC받았습니다! 혹시 위에 댓글 중 

"그리고 문제에서 주어진 순서대로가아니라 idx를 N-1부터 0까지 거꾸로 접근하면 로직의 잘못된점을 찾기가 힘듭니다. 정상적인 흐름이 아니기 때문입니다."

부분 조금만 알려주실수 있나요..?

탑다운은 뒤에서부터(N-1 --> 0) 바텀업은 앞에서부터(0-->N-1)로 알고있있어서

처음에 탑다운으로 해결하기 위해 거꾸로 뒤에서 부터 접근했는데(N-1-->0,현재 글에 쓴 코드대로)

AC받은 코드는 뉴딜님 조언대로 앞에서부터 접근했거든요,, 

제가 무엇을 헷갈리고 있는거죠?_?...왜 N-1부터 0까지 거꾸로 접근하는게 탑다운형식의 정상적인 흐름이 아닌지를 잘 모르겠습니다.흫

탑다운과 바텀업 방식의 차이점은

탑다운:큰 문제를 작은 문제로 쪼개서 푸는 것

바텀업:작은 문제를 큰문제로 합치는 것

입니다. 이 문제의 경우에도 idx를 0부터 접근하든, N-1부터 거꾸로 접근하든 결국 큰 문제를 작은 문제로 쪼개어서 푼다는 점입니다.

따라서 두 방식은 구현 자체도 크게 갈리게됩니다. 탑다운은 보통 재귀함수로 구현하고, 바텀업은 반복문으로 구현하게되죠.

아래의 간단한 피보나치함수를 보시면 이해가 편하실거같습니다.

점화식으로 내가 알고있는 정보를 쓰면 바텀업이고, 모르는 정보를 쓰면 탑다운입니다. 

@newdeal
감사합니다 깔끔하게 이해되었어요! 좋은밤되세용 ㅎㅎ호호