devbelly   10달 전

안녕하세요 이문제 풀다가 게시판에 글도 없고 테스트해볼 케이스도 많이 없어서 손으로만 한두개 넣어봣는데요

제가 작성한 코드는 CACHE 배열의 값이 작을떄는 잘 작동하는데 문제를 맞추기 위해

cache[2][301][301] -> cache[2][3001][3001]로 수정하니 아에 작동을 안하더라구요

코드자체는...맞는진 모르겠지만 아마 바텀업으로 바꾸면 되지 않을까? 라는 생각에 제가 작성한 코드를 바텀업으로 바꾸려고 했는데요

어떻게 해야할지 전혀모르겠습니다.

궁금한 점은

1. 제가 작성한코드가 아에 알고리즘이 틀렸나요?

2. 맞다면 해당 코드를 바텀업으로 어떻게 바꿀수 있나요?

newdeal   10달 전

안녕하세요.

우선, 이문제는 탑다운으로도 충분히 풀립니다. 저도 [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) )

devbelly   10달 전

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

devbelly   10달 전

@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까지 거꾸로 접근하는게 탑다운형식의 정상적인 흐름이 아닌지를 잘 모르겠습니다.흫

newdeal   10달 전

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

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

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

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

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

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

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

devbelly   10달 전

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

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