[Beakjoon/🥈SilverⅢ] 11726: 2×n 타일링

Intro

• 위 사진에서 확인할 수 있듯이 2 * n 크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 방법의 수를 구하는 문제이다.

👩 문제를 이해하기 위해서 n이 1,2,3,4일 경우를 각각 생각해보자!!

👩접근 방법

• 우리는 n이 1,2,3,4일 때 2 * 1과 1 * 2 블럭을 통해서 2 * n을 구현하는 방식을 쉽게 구할 수 있다!!

👩 이렇게 구해보니 약간의 규칙이 보이지 않는가!? 아래 그림을 다시 한 번 확인해보자!

• 넓이가 3인 직사각형을 만들기 위한 방식은 다음과 같이 두 분류로 나누어진다.
  • 넓이가 1인 블럭을 사용하고 나머지 넓이 2를 채우는 방법
    • 2를 채우는 방법은 넓이가 2인 직사각형을 만든는 방법
  • 넓이가 2인 블럭을 사용하고 나머지 넓이 1을 채우는 방법
    • 1을 채우는 방법 = 넓이가 1인 직사각형을 만드는 방법

👩 그렇다면 넓이가 4인 직사각형을 만들기 위한 방식은?!

• 넓이가 1인 블럭을 사용하고 나머지 넓이 3을 채우는 방법
  • 3를 채우는 방법은 넓이가 3인 직사각형을 만든는 방법
• 넓이가 2인 블럭을 사용하고 나머지 넓이 2를 채우는 방법
  • 2을 채우는 방법 = 넓이가 2인 직사각형을 만드는 방법

⇒ 👩따라서 n을 구하기 위해서는 n-1의 방법수와 n-2의 방법수를 더하면 된다는 것을 알 수 있다!

여기까지 왔다면 우리는 다음과 같은 생각을 할 것이다!

🙄 이전에 구한 값이 그 다음 구할 값을 위해 필요하고, 중복계산이 존재한다??

아! 디피를 사용해야겠다!

🙋‍♀️알고리즘

#21.10.06
n = int(input())
dp = [i for i in range(n+1)]
for i in range(4, n+1):
  dp[i] = dp[i-1] + dp[i-2]
print(dp[n] % 10007)

• 🙋‍♀️ 알고리즘은 매우 간단해 별도로 설명하지 않겠다!!

이번 문제도 매우 간단했다! 요즘 디피를 사용하는 문제가 많아 디피는 정확히 알고 넘어가는 것 같다! 히히 굳!

끝~~ ~(˘▾˘~)