📖Problem

1904번: 01타일

🔍Institution

이걸 어떻게 문제를 풀까 고민하다가, DP는 “점화식”이 가장 중요하다는게 떠올랐다.

점화식은 예제에 나온 값들 간의 “관계성”과 “규칙성”을 찾아야 한다. 따라서 그 부분에 대해 집중해서 보았다.

아이패드를 통해서 내가 아는 정보를 정리했다.

N = 1, 1개

N = 2, 2개

N = 3, ?개

N = 4, 5개

이거 마치 규칙이 피보나치 수열처럼 $A_i = A_{i-1} +A_{i-2}$ 처럼 되면 성립할 것처럼 보였다.

점화식은 $A_i = A_{i-1} +A_{i-2}$ 으로 세워서 코드를 짰다.

🔍Approach

• n의 값을 입력받는다.

• dp 테이블을 미리 정의해놓는다. 이때 0번 인덱스가 아닌 1번 인덱스부터 쓸 것이기 때문에 초기화할 때 배열의 크기를 신경써야 한다. 따라서 n+1이 아니라 n+2까지 여유있게 초기화한다.

• 내가 찾은 규칙은 $A_i = A_{i-1} +A_{i-2}$ 이다. 따라서, 이 식을 for문안에 넣어준다. 또한, 문제의 조건에서 15746의 나머지값을 출력하라고 하였으므로 이 부분도 반영한다

    dp[i] = (dp[i-1] + dp[i-2])%15746