[백준] 2×n 타일링 2 (동적계획법, DP, 11727번, Java)

q

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제는 2xn 타일링 문제에 이어지는 문제입니다.

 

위 그림과 같은 타일이 존재할 때 입력으로 n을 받아 2xn의 크기의 직사각형을 채우는 문제입니다.

 

타일을 채우다 보면 n = 5일 때 0~5까지의 타일링의 수는 다음과 같습니다.

 

• n= 0 ➡️ 1 (채우는 방법이 없으므로 1부터 시작)
• n= 1 ➡️ 1
• n= 2 ➡️ 3
• n= 3 ➡️ 5
• n= 4 ➡️ 11
• n= 5 ➡️ 21

위 타일링의 수를 생각해서 DP의 가장 핵심요소인 점화식을 도출해야 합니다.

 

좀 더 이해를 하기 쉽게 그림으로 표현하면 다음과 같습니다.

 

 

만약에 n = 3일 때를 보면

• n-1의 타일에서 2x1의 타일이 추가된 것을 볼 수있습니다.
• n-2의 타일에서 2x2를 채우는 경우는
  • 1x2 ➡️ 2개
  • 2x2 ➡️ 1개
  • 2x1 ➡️ 2개
    • 2x1의 타일을 2개를 배치하여 2x2를 채울 수도 있지만 이는 n-1에서 이미 사용되었기 때문에 제외합니다.
    • 따라서 2x2를 공간을 채우는 타일은 무조건 2가지 경우입니다.

따라서 점화식은  𝑑𝑝[𝑛]=𝑑𝑝[𝑛−1]+2 ×𝑑𝑝[𝑛−2]입니다.

 

 

---

점화식을 구했다면, 초기값을 세팅한 후 dp배열을 작성하면 됩니다.

 

이때 n이 2보다 작은 경우에는 dp [2]에 접근하지 않도록 하여 ArrayIndexOutOfBoundsException와 같은 예외가 발생하지 않도록 합니다.

 

 

 

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

 

[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기