백준 13301 타일 장식물 JAVA 풀이 (피보나치, DP)

🔗 문제 링크

https://www.acmicpc.net/problem/13301

---

📌 문제 개요

정사각형 타일을 이어 붙여 도형을 만들 때,
타일의 변 길이가 특정 규칙(피보나치 형태)을 따른다.

이때 N번째 도형의 둘레 길이를 구하는 문제이다.

---

📌 접근 방법

• 타일의 변 길이는 피보나치 수열
• 도형의 가로, 세로는 연속된 피보나치 값으로 구성됨
• 최종적으로 직사각형 형태가 되므로

둘레 = 2 × (가로 + 세로)

---

📌 핵심 아이디어

• 피보나치 수열을 이용해 변 길이를 계산
• 배열 없이 변수 2개로 최적화

a = 이전 값
b = 현재 값

 

반복하면서 갱신

---

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        long a = 1;
        long b = 1;

        for(int i = 2; i <= N; i++){
            long temp = a + b;
            a = b;
            b = temp;
        }

        System.out.println(2 * (a + b));
    }
}

---

📄 정리

• 피보나치 수열을 활용한 문제
• 배열 없이도 해결 가능 (공간 최적화)
• 최종 답은 둘레 공식 적용 : 2 × (F(N) + F(N+1))