- 점화식 바로 떠올리기
길이 N에 도착하기 직전의 마지막 동작은 무엇인가? → 타일 종류의 제약에 의해 +10 또는 20 예를 들어 N이 30이면 f(10)+20도 되고, f(20)+10도 됨
그 다음 생각해 볼 문제는 각 너비별로 어떤 경우의 수 가지는지? +20의 경우 정사각 타일 1개, 또는 직사각 타일 눕혀서 2개 붙일 수 있음 → 2가지 +10의 경우 직사각 타일 세로로 붙임 → 1가지
주의: +20을 '+10+10'으로 올라가는 건 이미 '+10'의 경우의 수에 포함됨! 즉 +20의 경우의 수 고려할 때 직사각 타일 세로로 2개 붙이는 경우는 한 번에 20을 늘리는 경우라고 보지 않고, +10을 2번 한 경우로 간주해 세지 않음
최종 점화식:
- 중복 피하기 (중요!)
이 모양을 더 쪼개서 이전에 계산한 '마지막 모양'으로 만들 수 있는가? 만들 수 있는 경우 중복!!!
이 문제에서 +10을 마지막 조각으로 썼다 (이전에 계산한 마지막 모양) 그럼 +20짜리 마지막 조각을 고를 때는, 절대로 중간에 세로로 쪼개지지 않는 녀석들만 골라야.
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
# 점화식은 마지막만 보자 (재귀 함수 / DP)
save_list = [1, 3]
n = int(input())//10
answer = 0
for index in range (n):
if index > 1:
new_value = int(save_list [index-1]) + (int(save_list[index-2]) * 2)
save_list.append(new_value)
answer = save_list[n-1] #index이므로 n-1, 코드블록 주의.
# 실수로라도 for문 안에 있으면 안 됨 (for문의 index가 n-1보다 작으면 에러 발생)
print (f'#{test_case} {answer}')