BOJ 9461: 파도반 수열

Note

동적 프로그래밍을 활용하여 특별한 점화식 패턴을 가진 수열 문제를 해결하는 문제입니다.

---

문제

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

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

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

문제 링크: https://www.acmicpc.net/problem/9461

입력

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

출력

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

예제

예제 입력 1:

2
6
12

예제 출력 1:

3
16

---

문제 원리 분석

이 문제는 동적 프로그래밍을 사용하여 해결할 수 있는 수열 문제입니다.

파도반 수열의 패턴

주어진 첫 10개 숫자를 살펴보면:

• P(1) = 1
• P(2) = 1
• P(3) = 1
• P(4) = 2
• P(5) = 2
• P(6) = 3
• P(7) = 4
• P(8) = 5
• P(9) = 7
• P(10) = 9

점화식 유도

수열의 패턴을 자세히 관찰해보면:

n	P(n)	관계
6	3	P(5) + P(1) = 2 + 1 = 3
7	4	P(6) + P(2) = 3 + 1 = 4
8	5	P(7) + P(3) = 4 + 1 = 5
9	7	P(8) + P(4) = 5 + 2 = 7
10	9	P(9) + P(5) = 7 + 2 = 9
11	12	P(10) + P(6) = 9 + 3 = 12
12	16	P(11) + P(7) = 12 + 4 = 16

패턴을 보면:

P(n) = P(n-1) + P(n-5)

왜 P(n-5)인가?

파도반 수열은 나선 모양으로 삼각형을 추가하는 과정에서:

• 현재 삼각형의 변의 길이는 5단계 전의 삼각형 변의 길이와 1단계 전의 삼각형 변의 길이의 합으로 결정됩니다.
• 이는 나선의 구조적 특성 때문입니다.

초기 조건

점화식을 적용하기 위해서는 최소 5개의 초기 값이 필요합니다:

• P(1) = 1
• P(2) = 1
• P(3) = 1
• P(4) = 2
• P(5) = 2

이후부터는 점화식 P(n) = P(n-1) + P(n-5)를 사용할 수 있습니다.

피보나치 수열과의 비교

특징	피보나치 수열	파도반 수열
점화식	F(n) = F(n-1) + F(n-2)	P(n) = P(n-1) + P(n-5)
의존성	2단계 전	5단계 전
초기값 개수	2개	5개

파도반 수열은 피보나치 수열보다 더 먼 과거의 값을 참조하는 특이한 패턴을 가집니다.

---

코드 구조 분석

제공된 코드

t = int(input()) # 2
 
dn = [0] * 101
dn[0:11] = [0,1,1,1,2,2,3,4,5,7,9]
 
for _ in range(t):
    n = int(input())
    
    for i in range(1, n + 1):
        if dn[i] > 0:
            continue
        dn[i] = dn[i-1] + dn[i-5]
    
    print(dn[n])

코드 분석

1. 테스트 케이스 처리

t = int(input()) # 2

• 테스트 케이스의 개수를 입력받습니다.
• 여러 테스트 케이스를 처리할 수 있도록 설계되었습니다.

2. 배열 초기화

dn = [0] * 101
dn[0:11] = [0,1,1,1,2,2,3,4,5,7,9]

배열 크기:

• N의 최대값이 100이므로 배열 크기를 101로 설정 (인덱스 0~100)

초기 값 설정:

• dn[0] = 0: 인덱스 0은 사용하지 않음 (편의상)
• dn[1] = 1: P(1) = 1
• dn[2] = 1: P(2) = 1
• dn[3] = 1: P(3) = 1
• dn[4] = 2: P(4) = 2
• dn[5] = 2: P(5) = 2
• dn[6] = 3: P(6) = 3
• dn[7] = 4: P(7) = 4
• dn[8] = 5: P(8) = 5
• dn[9] = 7: P(9) = 7
• dn[10] = 9: P(10) = 9

초기화 전략:

• 처음 10개 값을 미리 설정하여 작은 N에 대해서는 계산 없이 바로 반환 가능
• 점화식 적용 시 필요한 최소 5개 값(P(1)~P(5))은 확보됨

3. 동적 프로그래밍 적용

for _ in range(t):
    n = int(input())
    
    for i in range(1, n + 1):
        if dn[i] > 0:
            continue
        dn[i] = dn[i-1] + dn[i-5]
    
    print(dn[n])

테스트 케이스 루프:

• 각 테스트 케이스마다 N을 입력받고 P(N)을 계산합니다.

점화식 적용:

• for i in range(1, n + 1): 1부터 n까지 순회
• if dn[i] > 0: continue: 이미 계산된 값은 건너뜀
  • 이전 테스트 케이스에서 계산한 값을 재사용할 수 있음
  • 예: 첫 번째 테스트에서 n=12를 계산하면, 두 번째 테스트에서 n=6을 요청하면 이미 계산된 값을 사용
• dn[i] = dn[i-1] + dn[i-5]: 점화식 적용

최적화 포인트:

• 여러 테스트 케이스가 있을 때, 이전에 계산한 결과를 재사용
• 예를 들어 첫 번째 테스트가 n=12, 두 번째 테스트가 n=6이면:
  • 첫 번째 테스트에서 dn[1]~dn[12]까지 모두 계산
  • 두 번째 테스트에서는 dn[6]이 이미 계산되어 있으므로 바로 반환

코드의 특징

장점

1. 메모이제이션 활용: 여러 테스트 케이스에서 계산 결과를 재사용
2. 미리 초기화: 작은 값들을 미리 설정하여 불필요한 계산 방지
3. 효율적인 점화식 적용: 필요한 값만 계산

개선 가능한 점

더 명확하게 작성한다면:

t = int(input())
 
# dp[i] = P(i), 파도반 수열의 i번째 값
dp = [0] * 101
 
# 초기 조건
dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 2
 
# 점화식: P(n) = P(n-1) + P(n-5)
for i in range(6, 101):
    dp[i] = dp[i-1] + dp[i-5]
 
# 테스트 케이스 처리
for _ in range(t):
    n = int(input())
    print(dp[n])

이 버전의 장점:

• 초기 조건이 명확함
• 점화식 적용 범위가 명확함 (6부터 100까지)
• 테스트 케이스마다 반복 계산하지 않음 (미리 모두 계산)

---

시간 및 공간 복잡도

시간 복잡도

제공된 코드:

• 최악의 경우: O(T × N)
  • 각 테스트 케이스마다 최대 N번 반복
  • 하지만 실제로는 이미 계산된 값은 건너뛰므로 더 효율적

개선된 코드:

• O(100): 미리 1부터 100까지 모두 계산
• 각 테스트 케이스: O(1) (배열 접근만)
• 전체: O(100 + T)

공간 복잡도

• O(101): 배열 크기가 고정되어 있음
• N의 최대값이 100이므로 충분한 크기

---

예제 동작 과정

예제: t=2, 첫 번째 테스트 n=6, 두 번째 테스트 n=12

초기 상태:

dn = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 0, 0, ...]
      [0  1  2  3  4  5  6  7  8  9 10 11 12 ...]

첫 번째 테스트 케이스 (n=6):

• i=1: dn[1] = 1 > 0 → continue
• i=2: dn[2] = 1 > 0 → continue
• i=3: dn[3] = 1 > 0 → continue
• i=4: dn[4] = 2 > 0 → continue
• i=5: dn[5] = 2 > 0 → continue
• i=6: dn[6] = 3 > 0 → continue (이미 초기화됨)
• 출력: dn[6] = 3

두 번째 테스트 케이스 (n=12):

• i=1~10: 모두 이미 계산되어 있음 → continue
• i=11: dn[11] = 0 → 계산 필요
  • dn[11] = dn[10] + dn[6] = 9 + 3 = 12
• i=12: dn[12] = 0 → 계산 필요
  • dn[12] = dn[11] + dn[7] = 12 + 4 = 16
• 출력: dn[12] = 16

계산 과정 상세

P(11) 계산:

P(11) = P(10) + P(6)
      = 9 + 3
      = 12

P(12) 계산:

P(12) = P(11) + P(7)
      = 12 + 4
      = 16

---

수열의 특성

파도반 수열의 증가 패턴

n	P(n)	증가량
1	1	-
2	1	0
3	1	0
4	2	+1
5	2	0
6	3	+1
7	4	+1
8	5	+1
9	7	+2
10	9	+2
11	12	+3
12	16	+4

수열이 점점 빠르게 증가하는 것을 볼 수 있습니다.

점화식의 의미

P(n) = P(n-1) + P(n-5)는 다음과 같이 해석할 수 있습니다:

• 현재 단계의 값은 직전 단계와 5단계 전의 값의 합
• 이는 나선 구조에서 삼각형을 추가하는 규칙을 수학적으로 표현한 것

---

관련 알고리즘

• 동적 프로그래밍 (Dynamic Programming)