[백준] 9461번 파도반 수열 파이썬

[백준] 9461번 파도반 수열

---

✔️문제

분류

다이나믹 프로그래밍(dp), 수학(math)

문제 설명

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

✔️풀이

dp 문제로 점화식을 구해서 풀 수 있다.
문제를 보니, n번째 정삼각형의 변의 길이는 n-2번째 삼각형과 n-3번째 삼각형의 변의 길이의 합과 같다. 따라서 다음과 같은 식을 구할 수 있다.

위에서 구한 점화식을 코드로 구현했다.

❌시간 초과한 코드

import sys
input = sys.stdin.readline

def func(x):
  if x==1:
    return 1
  elif x==2:
    return 1
  elif x==3:
    return 1
  else:
    return func(x-2)+func(x-3)

t = int(input())
for _ in range(t):
  n = int(input())
  print(func(n))

재귀 함수를 사용해서 삼격형의 변의 길이를 구했다. 답은 정확하게 나왔지만, 중복되는 계산이 많이 생겨 시간이 초과한 코드이다.

✅통과한 코드

import sys
input = sys.stdin.readline
arr = [0, 1, 1, 1] + [0 for x in range(97)]

def func(x):
  if arr[x]:
    return arr[x]
  else:
    arr[x] = func(x-2) + func(x-3)
    return arr[x]

t = int(input())
for _ in range(t):
  n = int(input())
  print(func(n))

메모리제이션을 이용한 풀이이다.

1. arr를 만들어서 3번째 삼각형의 변의 길이까지 넣어주고, n이 100이 최대이므로 나머지 97개는 0으로 채웠다.
2. 만약 arr의 값이 0이 아니라면 이미 계산을 했다는 뜻이므로 해당 값을 리턴한다.
3. arr의 값이 0이라면 아직 계산하지 않았으므로 함수를 이용해 값을 계산하고, 계산한 값을 배열에 넣어준다.

🤔다른 사람의 풀이

import sys
input = sys.stdin.readline

t = int(input())
arr = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]

for i in range(11,101):
  arr.append(arr[i-2]+arr[i-3])

for _ in range(t):
  n = int(input())
  print(arr[n])

100번째까지의 변의 길이를 미리 구해서 배열을 만들고, 입력받은 값에 해당하는 배열 값을 출력했다.