[99클럽 코테 스터디 29일차 TIL] 파도반 수열 - 백준 9461

피보나치 수열과 비슷한 문제였다.

 

https://www.acmicpc.net/problem/9461

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 
첫 삼각형은 정삼각형으로 변의 길이는 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)을 출력한다.

출처: https://www.acmicpc.net/problem/9461

풀이 접근

이 수열의 규칙을 찾아보자.

1~3번 삼각형은 변의 길이가 1이다. 그리고 4~5번은 2다.

이후로는 3, 4, 5, 7, 9, 12 순으로 증가한다.

2, 3, 4, 5 의 차이가 1이고, 5, 7, 9가 2이다.

마지막으로 9, 12가 3인걸 보고 규칙을 발견했다.

1 1 1 2 2 3 4 5 7 9 12 ...
 0 0 1 0 1 1 1 2 2 3 ...

2와 3 사이 즉 5번째와 6번째 항부터 차이가 파도반수열과 같아진다.

마치 피보나치 수열이 1번째와 2번째항을 1로 고정해놓고 n > 3일때 An = A(n-1) + A(n-2)인 것과 같다고 생각했다.

파도반 수열도 비슷하게 점화식을 만들 수 있다.

A1 = 1, A2 = 1, A3 = 1, A4 = 2, A5 = 2,
n > 5 일때, An = A(n-1) + A(n-5)

따라서 앞의 5개의 항만 먼저 정해놓고 출발하면 된다.

var f = [1,1,1,2,2]

그리고 여러개의 테스트 케이스가 들어오기 때문에 만약 앞의 테스트 케이스에 의해서 답이 구해졌다면 다시 반복할 필요가 없다.

(0..<Int(readLine()!)!).forEach { _ in
    let num = Int(readLine()!)!
    print(f.count >= num ? f[num-1]: dp(n: num))
}

DP 함수는 다음과 같이 작성한다.

func dp(n: Int) -> Int {
    if n < 6 { return f[n-1] }
    for i in (f.count-5)..<n-5 {
        f.append(f.last! + f[i])
    }
    return f.last!
}

최종 코드 - Swift

var f = [1,1,1,2,2]
func dp(n: Int) -> Int {
    if n < 6 { return f[n-1] }
    for i in (f.count-5)..<n-5 {
        f.append(f.last! + f[i])
    }
    return f.last!
}
(0..<Int(readLine()!)!).forEach { _ in
    let num = Int(readLine()!)!
    print(f.count >= num ? f[num-1]: dp(n: num))
}

Conclusion

특정 수열을 명확하게 도출해야하는 경우에는 조금 쉽게 풀 수 있을 거 같다.