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

 

문제설명

입력 & 출력

 

나의 풀이

 

이번 문제는 가로는 2로 고정되어 있고 입력받은 N의 세로 크기만큼의 직사각형에 2x1, 1x2크기의 타일을 채워 넣을 수 있는 경우의 수를 구하는 문제입니다.

 

 

• 부분 문제의 중복
  • 큰 문제를 작은 부분 문제로 나눌 수 있습니다.
  • 위 그림처럼 n-1인 직사각형에 2×1 타일을 세로로 놓는 경우와, 크기가 n-2인 직사각형에 1 ×2 타일 두 개를 가로로 놓는 경우로 나눌 수 있습니다. 이렇게 작은 부분 문제들이 중복되어 나타납니다.

 

• 최적 부분 구조
  •  DP 문제는 작은 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있는 최적 부분 구조를 가집니다.

---

n이 1~5일때 타일을 배치할 수 있는 경우의 수는 위와 같습니다.

 

그림을 자세히 보면 n일 때는 n-1의 타일에 2x1타일이 추가된 것을 알 수 있고, n-2의 타일에 1x2의 타일이 2개 추가된 것을 알 수 있습니다.

 

따라서 점화식을 정리하자면 다음과 같습니다.  ➡️ dp [n]= dp [n−1]× dp [n−2]

 

 

---

 

풀이를 설명하자면 먼저 빠른 입력을 위해서 Buffer로 입력을 받아주고, dp 배열을 생성합니다. 문제에서 주어진 최대 입력 크기는 1000까지이므로, dp 배열의 크기를 1001로 설정합니다.

 

그리고 초기값을 설정하는 데 , 이때 n이 1보다 작거나 같을 경우에는 dp [2]에 접근하면 배열 인덱스 오류가 발생할 수 있기 때문에 조건문을 통해 걸러줍니다.

 

그리고 앞서 정의한 점화식을 통해 dp배열을 채워주는데, overflow를 방지하기 위해 문제에서 요구한 대로 10007을 나눈 나머지를 저장해 줍니다.

 

 

 

참고❗️

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

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