백준 2193번: 이친수 (JAVA) <다이나믹 프로그래밍>

 

문제 해석

 

자릿수 N이 입력값으로 주어질 때 만들 수 있는 N자리 이친수의 개수를 구해라

이친수의 첫자리는 1이며 1다음에는 무조건 0이 온다.

 

알고리즘

 

N=1인 경우 1 -> 1개

N=2인 경우 1 0 -> 1개

N=3인 경우 1 0 0 / 1 0 1 -> 2개

N=4인 경우 1 0 0 0 / 1 0 0 1 / 1 0 1 0 -> 3개

N=5인 경우 1 0 0 0 0/ 1 0 0 0 1 / 1 0 0 1 0 / 1 0 1 0 0 / 1 0 1 0 1 -> 5개

 

이를 통해 N번째인 경우 = N-1번째인 경우 + N-2번째인 경우 점화식을 도출할 수 있다. 

 

다이나믹 프로그래밍

 

이와 같은 형태를 다이나믹 프로그래밍이라고 한다.

하나의 문제를 작은 문제로 쪼개어서 작은 문제의 결과들을 저장하고 이를 보다 큰 문제들로 다시 키워가며 저장한 결과들을 이용할 때 사용한다.

재귀 방식과 유사하지만 재귀 방식과 달리 이미 알고있는 결과에 대해서는 저장된 값을 사용하여 효율성을 높여준다.

부분 문제의 결과를 재사용할 필요가 있을 때 재귀 방식 대신 다이나믹 프로그래밍을 사용하는 것 같다.

 

코드