숫자 n이 주어졌을 때 높이 2, 넓이 n만큼의 공간을 채우는 방법이 몇 개인지(경우의 수)를 구하면 된다.
그리고 그 값에서 10,007을 나눈 나머지를 값으로 출력하면 된다.
문제 이해
예)
숫자 1 : 2x1 사이즈
이 때는 세로2 x 가로1 사이즈의 세로로 길쭉한 모양의 직사각형 하나로 만드는 경우만 있다. 경우의 수는 1이다.
숫자 2 : 2*2 사이즈
세로 2 x 가로 2 사이즈이기 때문에 세로로 길쭉한 직사각형 2개 혹은 가로로 길쭉한 직사각형 2개 모두 가능하다. 경우의 수는 2이다.
이러한 방식으로 진행하다보면 아래와 같은 패턴이 발생하게 된다.
1과 2의 경우에는 앞의 수가 없기 때문에 직접 지정해주어야하고, n을 3이라고 했을 때 3부터는 아래와 같은 패턴을 확인할 수 있다.
[n의 경우의 수] = (n-1의 경우의 수) + (n-2의 경우의 수)
DP에 대한 기본 개념
- Dynamic Programming의 약자
- 동적 계획법 이라고도 한다.
- DP 방법에는 재귀와 반복문이 있다.
[재귀 Top-Down]
재귀의 경우 아래 하나의 메소드를 생성한 뒤 자기 자신을 반복해서 부르는 방법이다.
예를 들면 위와같이 n의 경우의 수를 구할 때 해당 내용을 메소드로 분리시켜놓은 뒤 n-1의 경우의 수, n-2의 경우의 수를 재귀호출을 통해 구하는 것이다.
하단의 코드를 보면 잘 이해할 수 있을 것이다.
[반복문 Bottom-Up]
반복문의 경우 dp라는 배열을 생성하여 반복문을 통해 dp라는 배열에 차곡차곡 값을 넣어준 뒤 내가 구할 위치의 값만 호출하면 된다.
마찬가지로 하단의 코드를 본 후 다시 읽으면 이해가 될 것이다.
입출력 형식
주의할 점은 값이 단순히 dp값이 아니라 그 값을 10007로 나눈 나머지 값을 출력해야한다는 점이다.
필자의 경우 문제를 잘 풀었음에도 오류가 발생했었는데, 반복문을 이용하여 값을 모두 구한 후 출력하면서 10007로 나눈 나머지를 출력하게 했다.
이 경우, dp값을 구하면서도 int 범위를 넘을 수 있어 틀리다는 결과가 나왔고, 반복문을 통해 dp값을 넣을 때 아예 10007로 나눈 나머지 값을 삽입하여 출력은 dp배열의 n번째 값을 바로 출력하게 했더니 해결되었다.
코드 이해
반복문
상단의 기본 코드에서 n이 1이나 2일경우 바로 출력되게 하였고, 이 코드를 줄이려면 아래와 같이 사용할 수도 있다.
if(n==1 || n==2) result = n;하단에 반복문을 돌릴 메소드를 따로 선언해주었다.
그리고 dp 배열에 10007로 나눈 나머지 값을 바로 삽입하고 상단에서는 dp[n-1]의 값을 바로 출력하게 했다.
n-1인 이유는 입력 받은 n만큼 배열을 선언했을 때 0부터 시작하니까 마지막 배열의 위치는 n이 아니라 n-1이다. 나는 배열 선언 시 n+1로 하지 않았기 때문에 마지막 출력값은 dp[n]이 아니라 dp[n-1]이 된다.
재귀
재귀 코드의 경우 마찬가지로 하단에 topdown이라는 이름의 메소드를 따로 생성해주었는데, 보면 알 수 있듯이 topdown을 여러번 호출하게 된다.
반복문보다 코드가 짧더라도 내부에서 돌아가는 횟수는 n이 크면 클수록 많아지기 때문에 코드를 짤 때 유의해야한다.
한줄평
같은 과정을 여러번 돌리는 코드일 경우 dp를 활용하면 훨씬 쉽게 풀 수 있을 것 같다. 개인적으로는 재귀보다 반복문 코드가 이해하기에도, 코드 측면에서도 더 나은 방법이라고 생각한다.
