[동적 계획법 1] [C++] 9461번. 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

 

입력

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

출력

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

해결 방법

처음 들어보는 새로운 수열이지만 그 규칙은 피보나치와 비슷하다.

피보나치의 점화식이 f(n) = f(n-1) + f(n-2) 였다면

N	1	2	3	4	5	6	7	8	9
P(N)	1	1	1	2	2	3	4	5	7

파도반의 점화식은 f(n) = f(n-2) + f(n-3) 임을 알 수 있다.

---

해결 방법

이번 문제부터는 C++로 풀어보려고 한다.

문제 풀이와 상관없는 내용이지만 2학기 때 알고리즘 과목에서 처음으로 파이썬을 접했고 지금까지 복습, 백준 문제풀이, 모각코 등에서 계속 파이썬만 썼었다. 이쯤하면 파이썬은 충분한 것 같다고 판단했고, 사실 주 언어로 쓰기에는 퍼포먼스나 기타 등등에서 조금 별로라고 생각해서 앞으로 2학기 객지설 때 배운 C++로 풀이를 해보려고 한다. 복습 겸 공부?

 

 

해결 과정

말이 길었지만 아무튼 위에서 구한 점화식을 그대로 구현하면 된다. 처음에는 vector를 사용했다.

배열을 사용해도 되지만 vector를 사용해보고 싶었다.

vector을 사용해서 문제를 해결하고 이후에 배열을 사용하면 메모리랑 시간이 줄어들거라는 생각에 배열로 구현해봤는데 똑같았다...!

 

아 그리고 주의할 점, vector나 배열을 선언할 때 자료형을 long long으로 해줘야지 문제를 통과할 수 있다.

 

최종 코드는

 

#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<long long> p;
    p.push_back(1);
    p.push_back(1);
    p.push_back(1);
    
    int t;
    int n;
    cin >> t;
    
    int i = 0;
    while (i < t){
        cin >> n ;
        if (n <= 3) {
            cout << 1 << endl;
        }
        else {
            for(int j = p.size(); j <= n; j++){
                p.push_back(p[j-2]+p[j-3]);
            }
            cout << p[n-1] << endl;
        }
        i++;
    }
    
    return 0;
}

 

파이썬으로도 한 번 풀어봤다.

 

def main():
    t = int(input())
    p = [0]*101
    p[1] = 1
    p[2] = 1
    p[3] = 1
    p[4] = 2
    
    for _ in range(t):
        n = int(input())
        if n <= 3:
            print(1)
        else:
            for i in range(5, n+1):
                p[i] = p[i-1] + p[i-5]
            print(p[n])

if __name__ == "__main__":
    main()

 

 

퍼포먼스 측면에서 C++보다 파이썬이 많이 아쉽다는 것을 볼 수 있다.

(+ 추가로)

파이썬으로 풀면서 알게된건데 점화식이 잘못됐다는 것을 알았다....ㅋㅋㅋㅋ;;

 

정확한 점화식은 f(n) = f(n-1) + f(n-5)가 맞다.

물론 f(n) = f(n-2) + f(n-3) 로 풀어도 동일한 값이 나온다. 하지만 파이썬의 경우 "틀렸습니다" 로 출력된다.

이유를 모르겠다. 입력 값의 범위인 1 ≤ n ≤ 100 의 값을 코드로 구현하여 비교해봤는데 모든 값이 같았다.

 

def main():
    t = int(input())
    p1 = [0]*101
    p2 = [0]*101
    
    p1[1] = 1
    p1[2] = 1
    p1[3] = 1
    p1[4] = 2
    
    p2[1] = 1
    p2[2] = 1
    p2[3] = 1
    p2[4] = 2
    
    check = True
    
    for _ in range(t):
        n = int(input())
        if n <= 3:
            print(1)
        else:
            for i in range(5, n+1):
                p1[i] = p1[i-1] + p1[i-5]
                p2[i] = p2[i-2] + p2[i-3]
            for i in range(n+1):
                if p1[i] != p2[i]:
                    print("값이 다른 것이 최소 1개 이상 있습니다.")
                    check = False
                    break
                
    if check == True:
        print("모든 값이 같습니다.")
                
if __name__ == "__main__":
    main()

 

p1은 f(n) = f(n-1) + f(n-5)의 점화식

p2는 f(n) = f(n-2) + f(n-3)의 점화식 을 사용한 리스트이다.

 

두 개의 리스트의 원소를 비교하여 한 개의 원소라도 다를 경우 메세지를 출력하게 구축하였다.

결과는 역시 예상과 같았다. 모든 원소가 같았다.

 

 

하지만 이유를 모르겠다...

메모리가 초과돼서 그런건가?

좀 더 고민해봐야겠다.