[BaekJoon] 백준 13301 타일 장식물 (Python / 파이썬)

BaekJoon 백준 13301 타일 장식물 문제는 정사각형 타일을 붙여 만든 형태로 한 변의 길이는 차례로 1, 1, 2, 3, 5, 8,...이다. N개의 타일로 구성된 직사각형의 둘레를 구하는 문제다. 메모이제이션, DP 동적 계획법 알고리즘 문제이며, 난이도는 Bronze 1다.

 

BaekJoon 13301 타일 장식물 문제 정보

출처

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

알고리즘 분류

- 동적 계획법(다이나믹 프로그래밍) DP Dynamic Programming, 메모이제이션 memoization

DP Dynamic Programming 동적 계획법 알고리즘과 예제

DP Dynamic Programming 동적 계획법 알고리즘과 예제

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

난이도

- 브론즈 1 / Bronze 1

 

타일 장식물 문제 요약

• 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다.
• 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 1, 1, 2, 3, 5, 8,... 과 같다.
• 타일의 개수 N(1 ≤ N ≤ 80)이 주어졌을 때, N개의 타일로 구성된 직사각형의 둘레를 구하여 출력한다.

 

문제 풀이 과정

1. 동적 계획법의 핵심 기술인 메모이제이션 기법을 사용하기 위해 index번 째 타일의 한 변의 길이를 원소로 갖는 memo 리스트를 선언한다.
2. memo [0] = 0, memo [1] = 1을 저장한다.
3. 타일 N개일 때 직사각형의 둘레는 N-1번째 타일의 한 변의 길이 * 2 + N번째 타일의 한 변의 길이 * 4라는 규칙을 찾을 수 있다.
4. 4번에서 알아낸 규칙을 식으로 표현하면, fibo(N - 1) * 2 + fibo(N) * 4이다.
5. 위 규칙을 이용하여 N개의 타일로 구성된 직사각형의 둘레를 구하여 출력한다.

 

코드 및 설명

• memo [] - n번 째 타일의 한 변의 길이를 저장한 리스트

def fibo(n):
    global memo
    if n < len(memo):
        return memo[n]
    else:
        memo.append(fibo(n - 1) + fibo(n - 2))
        return memo[n]


memo = [0, 1]
N = int(input())
print(fibo(N - 1) * 2 + fibo(N) * 4)

---

문제를 많이 풀 수록 DP가 얼마나 효율적인지 느끼고 있다.

 

BaekJoon 백준 13301 타일 장식물 문제를 파이썬 python의 동적 계획법 DP Dynamic Programming(다이나믹 프로그래밍), memoization 메모이제이션 기법을 사용하여 풀어보았다. 난이도는 Bronze 브론즈 1이다.