2133번 - 타일 채우기
제가 맨 처음에는 문제를 잘못 읽어서 2*1 1*2를 몇개를 사용 할 수 있는지 개수를 구하는 건 줄 알고 보니깐 다 채워서 몇가지에 경우가 나오는지 구하는 문제여서 도대체 어떻게 문제를 접근해야 할지 잘 모르겠습니다
혹시 이것을 dp를 어떤식으로 풀어야 할지 가르쳐 주세요 ㅜㅜ
N - 2개를 채우는 방법과 추가로 2칸짜리 타일을 채우는 방법과 N - 4개를 채우는 방법에 추가로 4칸짜리(독립적)
이렇게 n-6 개 추가 6칸 / n-8 개 추가 8칸..이런식으로
푸시면 될꺼같네요
전 점화식을 도저히 못 세우겠어서 bitmask dp를 사용해서 풀었던 기억이 나네요. 전형적인 완전 탐색을 짠 후에, 현재 읽고 있는 행과 열,visited 배열 중 근처에 있는 3~6개를 메모이제이션해도 풀립니다.
3*3 이나 3*5일때의 채울수있는 경우의 수는 없겠지요 ?
물론이죠
댓글을 작성하려면 로그인해야 합니다.
scared22 9년 전
제가 맨 처음에는 문제를 잘못 읽어서 2*1 1*2를 몇개를 사용 할 수 있는지 개수를 구하는 건 줄 알고 보니깐 다 채워서 몇가지에 경우가 나오는지 구하는 문제여서 도대체 어떻게 문제를 접근해야 할지 잘 모르겠습니다
혹시 이것을 dp를 어떤식으로 풀어야 할지 가르쳐 주세요 ㅜㅜ