백준 1904 - 01타일

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

1904번: 01타일

동적 프로그래밍을 사용하여 푼다.

 

길이 i의 타일을 만들 수 있는 경우의 수를 tile[i]이라고 할 때,

tile[i]은 다음과 같이 계산할 수 있다.

tile[i] = (tile[i-1]에 1을 추가하는 경우의 수) + (tile[i-2]에 00을 추가하는 경우의 수)

tile[i-2]에 11을 추가하는 경우는 중복되므로 제외한다.

 

결국 추가하는 경우의 수를 어떻게 계산하느냐가 문제의 핵심인데,

여러 경우를 확인하다가 다소 허무한 방식으로 답을 얻었다.

tile[1]부터 tile[5]까지의 값은 1, 2, 3, 5, 8이다.

굳이 값을 더 확인해보지 않아도 피보나치 수열을 이용하는 문제일 것이라는 느낌이 와서 그대로 답을 제출했다.

 

tile[i-1]과 tile[i-2]에서 1과 00 타일을 추가할 때,

굳이 여러 위치에 넣을 필요 없이 현재 배열의 맨 뒤에만 삽입하면

tile[i]의 모든 경우의 수를 얻을 수 있었다.

 

배운 내용 :

문제가 복잡해보일 때는

직관을 따라간 다음 이를 논리적으로 해석하는 방법이 나을 수 있다.