백준/ Silver3 문제 , 백준 파이썬 11727 , 2xn 타일링 2 , dp

백준/ Silver3 문제 , 백준 파이썬 11727 , 2xn 타일링 2

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

뭔가 이해가 되는 듯하면서 내가 생각한 방식대로 안되니까 헷갈리는게 있었던 문제이다.
예를 들면 dp(4) 의 경우 점화식으로는 이해가 되지만 나는 1,2 를 나열하는 식으로 접근하려고 해서
도대체 이걸 어떻게 일반화해야할까 고민했다

 

 

<문제 출처>

 

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

------------------------------------------------------------------------------------------------------------------------------

 

이 문제를 통해서 dp를 익혀 나갈 수 있다.

 

n=1 일 때 dp(1) =1

 

n=2 일 때 , dp(2) = 3

 

n=3 일 때, dp(3) = 5

 

n=4 일 때, dp(4) = 11

 

여기서 얻을 수 있는 점화식은

 

dp(n) = dp(n-1) + dp(n-2) 이다.

 

이 점화식을 적용하면 바로 풀린다.

 

 

 

 

이렇게 dp 로 접근하기전에 나는 1,2 를 나열 하는 식으로 문제를 풀려고 했었는데,

 

그냥 어떤식이 였는지만 알아보자. 굳이 쉽고 빠른 dp를 버리고 이걸 택할 이유도 없다.

 

 

자 n=1 의 경우 경우의 수는 한가지이다. 1x2 막대기 이거 하나밖에 못들어온다.

 

n=2 부터는 2x2 ,2x1 막대기 들이 들어오는데

 

1x2 막대기가 들어오는걸 제외하고 연속되는 2 x 2 에 들어올 수 있는 경우의 수는 2가지뿐이다.

 

 

즉, 1행에서만 봤을때 결국 경우의 수는 1칸 이냐 2칸이냐 차이다.

 

2칸이 차지하고있다면 x 2 만 해주면된다.

 

n=2 를 예를 들어보면

 

1행을 기준으로 들어올수있는건 

 

 

이렇게 두가지 이다.

 

거기서 두칸을 차지 하고있는 것에는 x 2를 해주는 것이다.

 

그러면 1+ 1x2 = 3 이라는 경우의 수가 나온다.

 

 

n=3 을 봐보자.

 

n=3 일때 1행에 들어올 수 있는 경우의 수는

 

1 + 1 + 1    => 1가지

 

1+ 2   => 1x2 => 2가지  (2의 갯수만큼 2를 곱해주면 된다)

 

2 + 1  => 1x2  => 2가지 

 

총 5가지가 나온다.

 

 

 

n=4 일때

 

1+1+1+1 => 1가지

 

1+1+2

1+2+1

2+1+1    => 2+2+2 => 총 6가지

 

2+2   => 2 x 2 => 4가지 (2가 두번나왔으므로 2번 곱해준다)

 

총 11 가지가 나온다.

 

 

결국 점화식 말고도

 

1과 2의 합으로 숫자를 나열하여 2의 갯수에 맞게 2를 곱해주는 식으로 계산을 해도 정답은 나온다. 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

정답