백준 9461 파도반 수열

문제링크

이 문제는 규칙을 찾지 못해서 팀원 분이 도움을 주셨다😭 오늘 다시 풀어보는데(벌써 어떤 규칙이었는지 까먹음) 대충 5단위로 뭔가 변했던것이 기억나긴했지만 그래도 스스로 규칙을 찾는데 성공했다😂

문제 이해

삼각형을 계속 이어 그려나가보면 아래와 같이 11번째 삼각형의 변의 길이는 12, ..., 16번째 삼각형의 변의 길이는 49 ...가된다. P(N)일때, N을 입력받았을때 출력값 P(N)을 출력해야한다.

P(N) = 출력값
P(1) = 1
P(2) = 1
P(3) = 1
P(4) = 2
P(5) = 2
P(6) = 3 #예제1 입력:6, 출력:4
P(7) = 4
P(8) = 5
P(9) = 7
P(10) = 9
P(11) = 12
P(12) = 16 #예제1 입력:12, 출력:16
P(13) = 21
P(14) = 28
P(15) = 37
P(16) = 49

문제 속 규칙

여기서 규칙을 잘 찾아보면
P(N-1) + P(N-5) = P(N)
예를들어, N=6
P(6-1) + P(6-5) = P(6)
(P(5)=2) + (P(1)=1) = P(6) = 3
다른 수들도 모두 대입해보면 적용된다는 것을 확인 할 수있다.

코드

이 규칙을 사용해 코드를 짜보면,

t = int(input())

for _ in range(t):
    lst = [1, 1, 1, 2, 2]
    #처음 숫자 5개는(P(1)~P(5))는 리스트에 미리 넣어줌
    n = int(input())
    for i in range(5,n+1):
    #인덱스 5부터 input값까지 규칙 적용해 리스트에 추가
        lst.append(lst[i-1] + lst[i-5])
    print(lst[n-1])
    #리스트의 인덱스를 출력해줘야하니 [n-1]

이렇게 넘나 간단한 코드가 나온다😙

첨에 짰던 코드

num = int(input())
nums = [0, 1, 1, 1, 2, 2]

for a in range (6,101):
    pattern = (nums[a-1]) + (nums[a-5])
    nums.append(pattern)

# print(nums)
for _ in range(num):
    j = int(input())
    print(nums[j])

규칙만 찾으면 금방 풀 수있는 문제인데 이런 문제는 규칙을 찾기까지가 넘나 힘들다😭