[백준] 11726번 2 x n 타일링

누군가에겐 쉽겠지만 이제 공부하는 나한테는 생각하는데 30분 정도 걸린 문제다..

만약 N이 1이라면 1x2 타일 하나밖에 쓸수 없으니 1이다.

N이 2라면 ? 1x2 타일 2개를 쓰는 방법 하나, 2x1 타일 1개를 쓰는 방법 하나. 2이다.

결국엔 N의 크기에 따라 뭘로 채울꺼냐는건데, 1x2로 채우는 방법, 2x1로 채우는 방법을 다 구해보면 될 것 같다.

(N-1) + (N-2) = 방법

N이 예를 들어 3이라면, 1x2 타일로 하나를 채우고(N-1)

2로 들어간다, 2에선 또 1x2 타일로 하나를 채우고(N-1)

1로 들어간다. 1에선 1x2 타일 하나밖에 채울수 없으니 방법 1개 완료

2로 돌아온다. 1x2 타일로 채우는 방법은 다 해봤으니 2x1 타일로 채우는 방법으로 돌아간다.

현재 가로 공간은 2가 남았으니 2x1 타일로 한번 채우면 더 이상 채울 수 없다. 방법 1개 완료

3으로 돌아온다

현재 (N-1) 쪽은 2를 리턴했다. 다음은 N-2로 들어간다

1로 들어간다. 1x2 타일 하나밖에 사용할 수 없다. 채웠으니 방법 1개 완료.

이렇게 N이 3이라면 총 방법 3을 리턴하게 된다.

<풀이방법 사진> (왼쪽 소스부터 1, 2, 3 순으로 보면 된다!)

그림 그리는데 엄청 힘들었다.

분명 난 포토샵을 만질 줄 아는데, 귀찮아서 그림판으로 했더니 오히려 시간이 더 걸린 것 같다.

문제를 보면 제한시간이 1초이다. 재귀 함수만으로는 1초내로 최대 1000개의 N을 구해낼 수 없으므로, 동적 계획법을 사용해야 한다.

<풀이 소스>

사실 재귀함수내에 dp를 사용하는 방법은 동적 계획법보단, 메모이제이션이라고 보는게 맞다.

동적계획법으로 만드는 방법은, 재귀함수를 지우고 반복문으로 dp[i] = dp[i-1] + dp[i-2] 를 해주면 된다.

재귀함수나 동적계획법이나 비슷비슷 하다.

사실 짤 순 있는데 귀찮다. 저 방법도 맞았다고 나왔으니 틀린 방법은 아니다. 

그리고 return dp[n] = (full(n-1) + full(n-2)) % 10007; 에서 왜 나머지 연산을 해주는지 궁금해할수도 있는데,

문제에서 방법을 구한것에 10007로 나눈 나머지를 출력하라고 되어있다.

다른 동적 계획법 문제를 보니 2xn 타일링 2 문제도 있었다.

결국 그 문제도 이렇게 풀어나가면 될 것 같다.