[C++] 백준 1904번 01타일

다이나믹 프로그래밍 문제.

점화식이 바로 보여서 쉽게 풀 수 있지만 왜 그렇게 되는지도 생각해서 풀어보았다.

 

문제풀이

나는 위에 같은 경우로 경우의 수를 나누었다.

그림에 대한 설명을 하자면

1. N = 1, 1 -> 1개
2. N = 2, 00, 11 -> 2개
3. N = 3, 001, 100, 111 -> 3개
4. N = 4, 0000, 0011, 1001, 1100, 1111 -> 5개
5. N = 5, 00001, 00100, 10000, 00111, 10011, 11001, 11100, 11111 -> 8개

여기까지만 해도 An = A(n-1) + A(n-2)라는 결과를 얻을 수가 있다.

그러면 왜 그렇게 되는 것일까?

An은 A(n-1)에서 한 자리가 추가되는 것이다.

한 자리가 추가되는 것은 무조건 타일 1이 추가되는 것이다. 그래서 A(n-1)의 개수와 같다.

 

또한 A(n-2)에서는 두 자리가 추가되는 것이다.

두 자리가 추가되는 경우는 00과 11이 추가되는 것이다. 그런데 우리는 이미 한 자리가 추가되는 경우에서 타일 1을

붙이는 경우를 고려했으므로 이 경우는 빼면 된다. 따라서 타일 00만 붙이는 경우를 생각하면 된다.

그래서 A(n-1) + A(n-2)의 경우와 같다.

 

코드로 살펴보겠다.

사용한 STL과 변수

먼저 이러한 모듈로 연산을 통해 식을 찾는 것은 왠만하면 long long 자료형을 사용하는 것이 좋다.

메인함수

코드는 그렇게 길지 않다. n을 입력받고 A1~A2까지는 먼저 따로 입력해준다.

그리고 반복문을 i=3부터 n까지 돌리고 DP의 Bottom Up방식으로 해결해주면 된다.

DP의 Bottom Up방식을 생각했다면 쉽게 바로 맞출 수 있었던 문제이다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.