SWEA[4869] : 종이붙이기

[SWEA[4869]번 문제]

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    N_list = [1,3]          # N 이 10일때와 20일때 초기값 설정
    # if N == 10 :
    #     print(f'#{tc} {1}')
    # elif N == 20 :
    #     print(f'#{tc} {3}')
    # else:
    #     for i in range(2, N // 10):
    #         N_list.append((N_list[i-2]*2) + N_list[i-1]) # 규칙 적용
    #     print(f'#{tc} {N_list[-1]}')
    for i in range(2, N // 10):
        N_list.append((N_list[i - 2] * 2) + N_list[i - 1])  # 규칙 적용
    print(f'#{tc} {N_list[N//10-1]}')

 # 규칙
 # N > cnt
 # 10 > 1
 # 20 > 3
 # 30 > 5   == 1*2 + 3
 # 40 > 11  == 3*2 + 5
 # 50 > 21  == 5*2 + 11
 # 60 > 43  == 11*2 + 21
 # 70 > 85  == 21*2 + 43

가로x세로 길이가 10x20, 20x20인 직사각형이 여러장 있다.

교실 바닥은 20xN 크기의 직사각형 형태이다 .

N은 10의 배수가 주어지는데, 종이를 붙이는 모든 경우를 찾아야 한다 .

이 문제는 파스칼의 삼각형 문제처럼 접근해서 풀이했다.

N = 10 일때, 경우의 수가 1개 밖에 없고, N = 20 일때, 경우의 수는 3개 이다.

그래서 새로운 리스트에 경우의 수를 초기값으로 초기화 해주었다. (N_list = [1,3])

입력값 예시로 30 일때는 5개, 50일때는 21개 70일 때는 35개가 출력예시로 주어졌다.

그래서 규칙이 뭘까 생각해보니 현재 인덱스의 값 = (리스트의 인덱스-2 의 값 * 2) + (리스트의 인덱스-1의 값) 이라는 규칙이 발견되었다.
( 다른 사람들의 풀이가 세개 정도 더 있었는데, 다들 신박하게 구하더라.ex)조합, 이전 인덱스값 + 2의 제곱 등등의 방법으로)

for 반복문으로 2부터 N//10( N이 10의 배수라서) 까지 반복해서 N_list에 (리스트의 인덱스-2 의 값 * 2) + (리스트의 인덱스-1의 값)을 추가시켜주었다.
그리고 리스트의 가장 마지막 인덱스에 해당하는 값을 출력하게 해주면 된다.