1055: 판 채우기

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

---

1. 문제

• 3 * N 의 판이 있습니다. 이 판을 1 * 1 짜리 블럭과 2 * 2 블럭들을 이용해서 빈틈없이 채우려고 합니다.
  길이 N이 주어 졌을 때, 몇 가지 방법으로 채울 수 있는지 구해 주세요.

 

---

2. 문제의 조건

• 1 <= T <= 10
• 1 <= N <= 100
• 1,000,000,007로 나눈 나머지를 출력

 

---

3. 문제 접근

• 시간 복잡도
  
  1초 이내의 시간에 총 1000개를 푸는 문제라서 O(N^2.66)시간 이내에 풀면 됩니다!

 

• 아이디어
  
  전형적인 dp문제 입니다.
  3*N의 판에선 총 2개만 고려하시면 됩니다.
  
  n이 길이가 1인 경우
  3 * 1을 채울수 있는 경우의수는 1*1을 3개 이용한 1가지입니다.
  
  또한, n이 길이가 2인 경우
  해당 2가지의 경우로 나뉘어집니다.
  이를 점화식으로 세우면 d(n-1) + 2*(n-2)가 됩니다.
  ※ n-3부턴 n-1와 n-2의 조합으로 만들 수 있으니 점화식에 계산(추가)하지 않습니다.
  
  dp와 메모이제이션을 이용한 점화식이므로 시간 복잡도는 O(N)이 되어 충분히 풀 수 있습니다.
  
  

 

---

4. 풀이 방법

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

 

---

5. 소스코드

• cjw-git.tistory.com/43

 

---

 

cjw.git@gmail.com