[백준][DP] 1904 : 01타일

문제

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

필요 지식

 - dynamic programming

해결 방법

 - 이런 수열? 비슷한 문제는 실제로 순서대로 해보며 규칙 발견하는 것이 좋다

 - N = 1 : 개수 1 (1)

 - N = 2 : 개수 2 (11,00)

 - N = 3 : 개수 3 (111,100, 001)

 - N = 4 : 개수 5 (0011,0000,1111,1100,1001)

 - N = 5 : 개수 8 (00111, 00100, 00001, 10011, 10000, 11111, 11100, 11001)

 - 규칙 발견

    - N = n 일때 n-1에서 1을 붙일 수 있고, n-2에서 00을 붙일 수 있다.

    - 하지만, 각각 1, 00을 앞 뒤로 붙일 수 있음

    - 그렇게 하면 중복이 발생함

     - n-1, n-2 둘다 앞에서만 붙인다던지, 뒤에서만 붙인 다던지 하면 중복 발생하지 않음

 - 다시 N을 보자.

 - N = 1 : 개수 1 (1)

 - N = 2 : 개수 2 (11,00)

 - N = 3 : 개수 3 (001 / 111,100)  = (00 + N[1], 1+ N[2])

 - N = 4 : 개수 5 (0011,0000 / 1111,1100,1001) = (00 + N[2], 1+ N[3])

 - N = 5 : 개수 8 (00111, 00100, 00001, 10011, 10000, 11111, 11100, 11001)

주의할 점

 - 메모리 생각

• 하드웨어 메모리 
• 하드웨어에 따라 배열 크기 1000001이 안 만들어 질 수 있다.
• 그때에는 배열 크기 적게 해서 돌아가나 보기
• 프로그램 내 메모리 
• unsigned long long을 tile의 데이터 타입으로 하더라도 구하는 중에 overflow남
• 따라서, 출력문에서 15746을 나누는게 아니라, tile계산 중에 나눠야 함

코드