1056: 화장실 타일 채우기

Link : judge.koreatech.ac.kr/problem.php?id=1056

---

1. 문제

• 광성이는 꿈에 그리던 집을 가지게 되었습니다. 평소 살고 싶었던 자연에 동화된 집으로 창밖에는 바다가 보이고, 뒷면에는 산이 있어서 시간이 나면 산에도 언제든 올라갈 수 있습니다.
  그런데 이 집엔 한가지 단점이 있었는데, 전에 살던 사람이 난장판으로 화장실을 사용했는지 화장실 타일 일부가 깨져 있었습니다. 깔끔한 광성이는 이 모습을 보기 싫어서 근처 인테리어 물품 판매점에 타일을 사려고 찾아가보니 구입할 수 있는 타일이 안타깝게도 한 종류 밖에 없었습니다. 인터넷 배송으로 더 좋은걸 살까도 싶었지만 당장 화장실을 바꾸고 싶어서 그 자리에서 타일을 충분한 양을 구매 했습니다.
  구입한 타일은 가로 길이 2, 세로 길이 1인 타일로 산뜻한 민무늬에 평소 좋아하던 초록색을 띄고 있습니다.
  깨진 부위를 뜯어내고 나니 높이는 2이고 너비는 N인 횡한 벽이 드러났습니다. 타일이 정방형이 아니여서 붙이는 방법에 따라 여러가지 모양이 나올 수 있음을 안 광성이는 갑자기 한가지 궁금한점이 생겼습니다.
  가지고 있는 타일로 벽을 채울때 몇가지의 방법으로 채울 수 있을까요?
  호기심은 왕성하지만 도무지 이걸 어떻게 계산해야 할지 모르는 광성이를 위해 너비 N이 주어졌을 때 벽면을 채울 수 있는 방법의 수를 알려주는 프로그램을 작성 해 주세요.

 

---

2. 문제의 조건

• 1 <= T <= 10 (테스트 케이스 개수)
• 1 <= N <= 100 (벽의 너비)
• 1,000,000,007로 나눈 나머지 출력

 

---

3. 문제 접근

• 시간 복잡도
  
  1초 이내의 시간에 총 1000개를 푸는 문제입니다. O(N^2.66)시간 이내에 해결 하면 됩니다.

 

• 아이디어
  
  전형적인 dp문제입니다!
  2*N의 판에서도 총 2개의 케이스만 고려하시면 됩니다.
  
  n이 1인 경우
  
  2*1의 판을 세로로 놓으시면 됩니다.
  총 1가지의 케이스가 나옵니다.
  
  n이 2인 경우
  2*1의 판을 가로로 2개 놓으시면 됩니다.
  총 1가지의 케이스가 나옵니다.
  ※ 2*1의 판을 세로로 2개 놓으시면 n=1일 경우와 겹치므로 놓지 않습니다.
  
  dp와 메모이제이션을 이용한 점화식이므로 시간 복잡도는 O(N)이라서 충분히 해결 할 수 있는 문제입니다.

 

---

4. 풀이 방법

• dp를 수행 할 배열을 n+1만큼 만들어줍니다.
• 2 * 1(n)일 땐 경우의 수가 1개이고 2 * 2(n)이 되면 경우의 수가 2가되므로 dp[1] = 1이되고 dp[2] = 2가 됩니다.
• 1과 2일 때 구했으니 3번째부터 n+1까지 점화식을 수행합니다.
• dp[n]번째를 출력합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/45

 

---

 

cjw.git@gmail.com