BOJ 9461번 : 파도반 수열 (Python/Silver 3)

9461번: 파도반 수열

---

설명

첫 정삼각형이 1일 때 변의 길이는 1이다. 아래와 같은 그림처럼 나선형으로 삼각형이 이어진다. 만약 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 가 있을 때 10번째 삼각형의 변의 길이는 9이다.

N이 주어졌을 때 N번째 삼각형의 변의 길이를 출력하면 된다.

 

풀이

• Dynamic Programming 문제

 

피보나치 수열과 비슷하다. 규칙성을 찾아보면 아래 그림에서 1번째와 2번째를 더하면 4번째 값이 나온다. 고로, 4만큼 차이가 난다. 

또한, 아래 그림을 보면 1번째와 5번째를 더하면 6번째 값과 같다. 

이러한 규칙성을 참고해 구현한다. 

 

Solution

sol.1

#23:11 - 23:36

import sys
input = sys.stdin.readline

t = int(input()) #테스트 케이스

def DP(n):
    dp = [0] * (n)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 1

    for i in range(3, n):
        dp[i] = dp[i - 3] + dp[i - 2]
    return dp[n-1]

for _ in range(t): #테스트 케이스만큼 반복
    n = int(input())
    if n == 1 or n == 2 :
        print(1)
    else:
        print(DP(n))

 

sol.2

#다른 풀이

t = int(input())
 
l = [1,1,1,2,2]
for i in range(5, 100):
    l.append(l[i-1]+l[i-5])
 
for _ in range(t):
    n = int(input())
    print(l[n-1])

 

---

👩‍💻 회고

처음 제출했을 때 'IndexError'가 떴다. 반례를 생각해보니 dp리스트가 n만큼 생성되게 했는데 n = 1, 2 일 때는 공간이 없어서 리스트에 값을 넣지 못하고, 3번째부터 for문을 돌게 했는데 i가 3일 때는 돌지 못한다는 걸 깨달았다. 그래서 DP 함수 내에서 조건식을 추가했는데 다시 에러가 떴다.

 

n이 2이하일 때 리스트 0부터 2번째 인덱스까지 값을 넣게 했더니 n이 1일 때에 문제가 생겨버리는 것이었다. 조건식을 한번에 걸어버려서 main에 n이 1일 때와 2일 때를 따로 나눴더니 에러 없이 제출이 됐다.

 

첫 번째 풀이(내 풀이)와 두 번째 풀이(다른 사람들 풀이)의 메모리와 시간은 같다. 그러나 간결한 풀이는 두 번째 풀이이다. DP라고 해서 복잡하게 생각한 것 같다. 좀 더 깔끔한 풀이가 나올 수 있게 생각을 오래 해야 할 것 같다.