백준알고리즘 #9461 파도반수열 Java

백준알고리즘 #9461 파도반수열 문제

삼각형을 이어붙여 다음 삼각형의 변의 길이를 구하는 문제이다.

규칙을 찾아보면 처음 P(1), P(2), P(3)은 1로 고정이고 그 다음부터 P(n-2)+P(n-3) = P(n) 이 되는것을 알 수 있다.

재귀함수를 사용하여

재귀함수

다음과 같이 나타낼 수 있다.

다만 이렇게 만들게 된다면 큰 수를 표현할 때 시간이 엄청 오래걸리게 된다.

예를 들어 80번째의 수를 구하기 위해서는 78, 77 번째의 수를 구해야 하는데 이때 각 78 77번째의 수를 구하기 위해서는 또 75 76, 74 75번째의 수를 구해야 하고 ... 이런식으로 수없이 많은 계산을 반복해야 한다.

이 시간을 줄이기 위해 배열을 생성하여 배열에 각 값들을 저장해 두게 되면 반복되는 계산이 줄어들게 되므로 시간이 단축되는 효과가 있다.

다이나믹 프로그래밍

이처럼 pa라는 배열 객체를 생성한 후 여기에 각각의 값들을 저장해 둔다면 80번째의 수를 구할 때 이미 구해놓은 78, 77번째 수를 더하기만 하면 되므로 시간초과 없이 문제를 해결할 수 있다.

백준알고리즘 #9461 코드

이러한 코드를 다이나믹 프로그래밍이라고 한다.

다른 말로 동적 프로그래밍 이라고 하는데 이 방법중 하나가 위에서 사용한 메모이제이션 기법이다.

메모이제이션 기법이란 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법이다.

 

다이나믹 프로그래밍 기법은 차후에 용어 정리를 하면서 자세히 다뤄보도록 할 예정이다.