busyhuman   7달 전

짝수일때 타일의 독립적인 부분

dp[i][0] = 3, 9 , 27 ...

그리고 겹치는 부분

dp[i][1] = 0, 2, 14...

로 해서 d[n][0]+d[n][1]로 답을 구해보고 싶은데

어떻게 구해야할 지 모르겠습니다. 특히 겹치는 부분이요.

어디서부터봐야 식을 쉽게 짤 수 있을까요?

코드는 갈아엎어서 없습니다.

joonas   7달 전

왼칸부터 채워나가면 나올 수 있는 다음 판의 상태가 2가지밖에 없어요.

그 2가지 판을 채우는 경우를 재귀로 구하시면 될 거 같아요.

AA#
BB#
CC#

AA#
B##
B##

A##
A##
BB#

첫번째는 다시 꽉찬 3N 이 나오는데 두번째, 세번째는 2줄+3줄~ 이네요. 이렇게 2가지 상태밖에 없고 겹치는 경우는.. 없을 거 같은데요?

###
###
X##

를 채우는건

AA#
BB#
XCC

A##
A##
X##

이렇게 2개밖에 없겠네요.

busyhuman   7달 전

joonas 예상 외의 답변이라.. 잘 이해가 안됩니다. 제가 말한 dp[i][1]에 대해서 설명해주신건가요? A,B,C,#이 무얼 뜻하는지도 궁금합니다. 

joonas   7달 전

dp[i][0] 에서 i가 i번째 줄까지의 상태 아닌가요? 저도 "짝수일때 타일의 독립적인 부분", "겹치는 부분" 이라는게 뭘 말씀하시는 지 잘 이해를 못했어요.

#는 빈칸을, AA BB 는 같은 알파벳끼리 하나의 덩어리를, X는 이미 채워진 칸을 표현했습니다. 타일이 그 모양으로 있는거지요. 
처음 3개의 모양이 3xN 에서 나올 수 있는 (왼쪽칸부터 채우는) 경우이고, 나머지는 그렇게 채운 과정에서 첫칸이 2줄+이후에 3줄을 (왼쪽칸부터) 채우는 경우입니다.

아무래도 이 링크가 더 설명을 잘 했을 것 같네요. 도움이 되시면 좋겠습니다.

busyhuman   7달 전

joonas 감사합니다 참고하고 다시 풀어보겟습니다

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