sgc109   8년 전

이 문제를 풀기 위해 우선 재귀적인 무식한 방법을 생각해봤습니다. 예를들어 스티커 판이

0 1 2 3 4

5 6 7 8 9

로 있을 때

처음에는 0을 선택하는경우와, 5를 선택하는 경우 두가지를 생각할 수 있고

만약 0을 선택하면

x x 2 3 4

x 6 7 8 9

가 남으므로 다음번엔 6을 선택하는 경우와 7을 선택 하는경우 두가지가 생기므로(2는 어차피 6을 선택한 뒤에도 선택할 수있으므로 다음번에 고려하기때문)

2가지 의 케이스씩 계속 나온다는 것을 알아내어

n의 최대값이 100,000 이기 때문에 최악의 경우 함수 호출 횟수가 2^100000 정도 라는 것을 알았습니다.(물론 둘중에 어떤것을 선택하느냐에 따라 최종적으로 선택하게 되는 스티커의 개수가 달라지지만 지그재그로 선택할 때 처럼 한 열당 하나를 선택할 수 있다고 간주해서 최악의 케이스를 보면)


이것은 적어도 제가 살아 있는 동안은 해결할 수 없을 것 같고 중복되는 것도 많은것 같아서

어제 JM북에서 공부했던 분할 정복을 활용해 볼 수 있을 것 같은 느낌에 코드를 작성해봤습니다.

그 코드가 아래의 코드입니다. 전체 스티커판을 계속 절반 덩어리 2개로 나누는데 나누는 경계부분이

선택 ㅣ 선택

미선택 ㅣ 미선택

미선택 ㅣ 미선택

선택 ㅣ선택

같이 선택이 좌우로 붙어있는 경우나

상하로 붙어있는 경우는 조건에 부합하지 못하므로 제외해야하며

미선택 | 미선택

미선택 | 미선택

은 절대로 최대값이 나올수 없으므로 제외해야하기때문에

각각의 함수 호출 부분에서

경계를 기준으로 왼쪽과 오른쪽의 선택현황에 대해 위에서 제외한것을 빼고 나머지 6가지의 케이스들 중에 최대값을 고르도록

설계해보았습니다. 그런데 제출을 하고보니 시간초과가 나서 함수 호출횟수를 대략 계산해보았더니


6^(log2100000) 정도가 되는것을 확인했습니다. 대략 수 조 번이 되는것 같은데 이전보다는 훨씬 줄어든 횟수이지만 이것도

문제에서 제시된 시간안에 돌아갈 수 없다는 것을 알았습니다..

그래서 좀더 생각해 보니 중복되는 경우가 많이 있다는 것을 알게되었고

함수의 인자값 들을 인덱스로 갖도록 메모이제이션을 사용하려고 보았더니

100,000 x 100,000 만 해도 100억이 되어 메모리가 부족해도 한참 부족하다는 것을 알게되었습니다...


어떻게 하면 좋을까 계속 생각하고있는데 막혀서 진행을 할 수가 없습니다.. @hongjun7

이런식으로 생각을 전개하는게 맞는건가요..? 아니면 아예 접근 방식을 달리해야할까요?

만약 이렇게 하는방법도 맞는거라면 여기서 어떤식으로 풀어나가야할지 힌트부탁드립니다!

rlatkddn212   8년 전

우선 scanf로 바꾸셔야 할듯 cin으로 하니 시간 초과 나오네용..

함수의 인자값을 줄이면 충분히 메모이제이션으로 가능해요.

저는 왼쪽부터 시작해서 아래위 둘중 하나 선택하면서(어떨때는 선택안하고) 오른쪽으로 한칸씩 진행하도록 했더니 겨우 통과되더군요.

sgc109   8년 전

@rlatkddn212 메모이제이션을 어떤식으로 하면 좋을지 힌트좀 주실수있나요??

rlatkddn212   8년 전

재귀로 하니깐요.

0 1 2 3 4

5 6 7 8 9

이렇게 상태가 있으면

다음 상태로 가는 방법이 3가지가 있죠.

0 을 고를때

x x 2 3 4

x 6 7 8 9

5를 고를떄

x 1 2 3 4

x x 7 8 9

안고를때

0 1 2 3 4

5 6 7 8 9

이렇게 3가지 타입중 고를 타입과 index 값을 다음 상태로 넘겨줘요.

그럼 int cache[3][100001]; 이렇게 메모라이제이션할 수 있겠죠.

rlatkddn212   8년 전

@sgc109 그러니깐 선택한 방법 모두 저장할 필요없이 바로 직전에 고른 방법만 알아도 최대값을 얻을수 있다능..

baekjoon   8년 전

지금 질문한 방법과 위에 달려있는 답변을 가지고 조금만 고민하면 DP에 대한 개념을 확실히 이해할 것 같습니다?

h0ngjun7   8년 전

rlatkddn212 님이 잘 설명해주셨네요 ㅎㅎ

sgc109   8년 전

@rlatkddn212 그렇군요~! 좋은 말씀 감사드립니다~!

@baekjoon 곰곰히 한번 고민해보겠습니다 감사합니다~!

@hongjun7 든든한 지원 감사드립니다~!

모두모두 감사드립니다~!

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