scared22   9년 전

제가 맨 처음에는 문제를 잘못 읽어서 2*1 1*2를 몇개를 사용 할 수 있는지 개수를 구하는 건 줄 알고 보니깐 다 채워서 몇가지에 경우가 나오는지 구하는 문제여서 도대체 어떻게 문제를 접근해야 할지 잘 모르겠습니다

혹시 이것을 dp를 어떤식으로 풀어야 할지 가르쳐 주세요 ㅜㅜ

adream   9년 전

N - 2개를 채우는 방법과 추가로 2칸짜리 타일을 채우는 방법과
N - 4개를 채우는 방법에 추가로 4칸짜리(독립적)

이렇게 n-6 개 추가 6칸 / n-8 개 추가 8칸..이런식으로

푸시면 될꺼같네요

koosaga   9년 전

전 점화식을 도저히 못 세우겠어서 bitmask dp를 사용해서 풀었던 기억이 나네요. 전형적인 완전 탐색을 짠 후에, 현재 읽고 있는 행과 열,visited 배열 중 근처에 있는 3~6개를 메모이제이션해도 풀립니다.

scared22   9년 전

3*3 이나 3*5일때의 채울수있는 경우의 수는 없겠지요 ?

koosaga   9년 전

물론이죠

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