[백준] 9461번 : 파도반 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

9461번: 파도반 수열

 

1. 문제 설명

2. 풀이과정

해당 문제는 한가지 규칙을 찾으면 쉽게 해결할 수 있다.

삼각형의 한 변의 길이를 살펴보면 5개까지는 별 다른 규칙이 없어보이지만 6번째 삼각형의 변의 길이부터는 규칙이 생기는 것을 볼 수 있다.

바로 이전 삼각형의 한 변의 길이에 5번째 전 삼각형의 한 변의 길이를 더하면 다음 삼각형 추가되는 삼각형의 한 변의 길이가 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 테스트 케이스의 개수를 입력받는다. T = int(sys.stdin.readline())
3. 테스트 케이스 개수만큼 반복하며 for _ in range(T)
4. 한 변의 길이를 구할 삼각형의 번호를 입력받는다. N = int(sys.stdin.readline())
5. 처음 5개의 삼각형까지는 규칙이 없으므로 5개 삼각형의 한 변의 길이를 담은 리스트를 생성한다. li = [1, 1, 1, 2, 2]
6. 만약 입력받은 삼각형 번호가 5 이하이면 if (N <= 5)
7. 해당 번호의 삼각형 한 변의 길이를 출력한다. print(li[N - 1])
8. 반면에 입력받은 삼각형의 번호가 5를 넘어갔다면 else
9. 해당 번호까지 삼각형의 한 변의 길이를 구해나가야 한다.
10. 하여 변의 길이를 참고할 시작 위치 값을 저장해줄 변수를 생성하고 초기화해준다. i = 0
11. 삼각형의 변의 길이를 저장한 리스트가 N개가 될 때까지 반복하며 while (len(li) < N)
12. 해당 위치의 삼각형의 변의 길이와 이후 4개 앞에 있는 삼각형의 변의 길이를 더하여 그 결과를 리스트에 추가한다. li.append(li[i] + li[i + 4])
13. 이는 다음 삼각형의 바로 이전 삼각형의 한 변의 길이와 5번째 전 삼각형의 한 변의 길이를 더한 결과이다.
14. 변의 길이를 참고할 시작 위치를 1 증가시킨다. i += 1
15. 해당 번호의 삼각형 한 변의 길이를 출력한다. print(li[N - 1])

반응형

3. 소스코드

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    N = int(sys.stdin.readline())

    li = [1, 1, 1, 2, 2]
    if (N <= 5):
        print(li[N - 1])
    else:
        i = 0
        while (len(li) < N):
            li.append(li[i] + li[i + 4])
            i += 1

        print(li[N - 1])