[BOJ] 13301 타일 장식물 - JAVA

1. 문제

13301번: 타일 장식물

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.

1, 1, 2, 3, 5, 8, ... 

지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

타일의 개수 N(1 ≤ N ≤ 80)이 주어졌을 때, N개의 타일로 구성된 직사각형의 둘레를 구하는 프로그램을 작성하시오.

---

2. 풀이

피보나치 수열이다. 단, 타입에 주의해야 한다. (long타입)

N이 6일 때 가장 큰 사각형의 길이는 8이다. N이 5일때 가장 큰 사각형의 길이는 5다.

그림으로 봤을 때, 6개의 타일로 구성된 직사각형의 둘레는 8*4 + 5*2로 구할 수 있다.

따라서 N개의 타일로 구성된 직사각형의 둘레는

dp[N]*4 + dp[N-1]*2이다.

 

피보나치 수열을 전부 구한 후 위의 식을 활용해서 둘레를 구해서 출력한다.

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		long[] dp = new long[81];
		dp[1] = dp[2] = 1;
		for(int i=3;i<=N;i++) dp[i] = dp[i-1]+dp[i-2];

		System.out.println(dp[N]*4+dp[N-1]*2);
	}
}

---

3. 결과

dp로 문제를 풀 때 초기값을 줘야한다면 배열 크기를 고정하는 게 낫다! long[N+1]하고나서 dp[1]=dp[2]했더니 N이 1일 때 인덱스 에러가 났다.