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

│문제

 

9461번: 파도반 수열

 

 

│풀이

T=int(input())

memo ={1:1,2:1,3:1,4:2,5:2}

def equilTriangle(n):

    if n in memo:

        return memo[n]

    memo[n]=equilTriangle(n-5)+equilTriangle(n-1)

    return memo[n]

for i in range(T):

    print(equilTriangle(int(input())))

 

│설명

 

왼쪽의 그림을 보고 규칙을 찾기 위해 첫 번째 삼각형을 A1, n번째 삼각형을 An으로 가정할 때 작성하면 다음과 같다.

A1=1, A2=1, A3=1                              A8 = 5 (A3+A7) 

A4=2 (A2+A3)                                    A9 = 7 (A4+A8)

A5 = 2 (A4)                                        A10 = 9 (A5+A9)

A6 = 3 (A3+A5)                                  A11 = 12 (A6+A10)

A7 = 4 (A2+A6)                                  A12 = 16 (A7+A11)

 

n이 6부터 An=A(n-5)+A(n-1)인 것을 알 수 있다. 이를 토대로 재귀를 활용하여 아래와 같이 코드를 작성하였다.

 

T=int(input())

def equilTriangle(n):

    if n>5:

        return equilTriangle(n-5)+equilTriangle(n-1)

    elif n>3:return 2

    else: return 1

for i in range(T):

    print(equilTriangle(int(input())))

 

하지만 다이나믹 프로그래밍 문제의 경우 재귀에서 계산했던 과정을 다시 계산하는 경우가 많아 시간초과의 문제를 겪게 된다.예를 들어 equilTriangle(n-5)+equilTriangle(n-1) 을 계산하기 위해서는equilTriangle(n-5)는  equilTriangle(n-1)를 거쳐 가므로 중복계산을 한다.

 

 

DP와 메모이제이션에 관한 내용은 추후 자세하게 포스팅하겠다.

 

 

A1 ~ A5 이후부터 명확하게 규칙이 보이므로 메모지에션에 memo ={1:1,2:1,3:1,4:2,5:2}   A1부터 A5를 기본값으로 표기하고, 재귀를 통해 메모제이션에 이미 있는 값이면 계산할 필요 없이 생략 후 메모제이션에 없는 값만 추가적으로 계산을 진행하면 시간초과문제를 보다 쉽게 해결할 수 있다. 필자가 느끼기에 9461번 문제의 파도반 수열 문제는 DP문제의 개념을 익히고, 메모제이션 활용에 좋은 문제라고 생각한다.

 

│풀이 (C언어)

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

long long memo[100] = { 1,1,1,2,2 };

long long equilTriangle(int n) {

    if (memo[n-1] != 0) return memo[n-1];

    else {

        memo[n-1] = equilTriangle(n - 5) + equilTriangle(n - 1);

        return memo[n-1];

    }

}

int main(void) {

    int t = 0;

    scanf("%d", &t);

    for (int i = 0; i < t; i++) {

        int n = 0;

        scanf("%d", &n);

        printf("%lli\n", equilTriangle(n));

    }

    return 0;

}

 

│설명  (C언어)

 

keypoint 1 - DP문제에서는 int를 벗어나는 정수가 있다고 간주해야 한다.

첫 풀이에서  아래와 같이 메모이제이션을 int로 하는 실수가 있었다.

int memo[100] = { 1,1,1,2,2 };

int equilTriangle(int n)

DP문제유형 같은 경우 n이 증가 함에 따라 수가 기하급수적으로 늘어나기에 

c언어에서의 int자료형은 -2,147,483,648~ 2,147,483,647 범위만 가능하기에 더 범위가 큰 long long 자료형을 사용하여 풀이하여야 한다.

 

ps) long long 형식의 출력

%u          +- 부호 없는 정수로 출력

%lld        signed long long 형식을 출력

%llu        unsigned long long 형식을 출력

%lli         long long 10 진수 출력

%llo        long long 8 진수 출력

%llx        long long 16 진수 출력