2133번 타일채우기(DP) - ☆

#문제링크 : https://www.acmicpc.net/problem/2133

<전략>

1. N번째에 올 수 있는 타일의 종류는 N-2번째에 올 수 있는 타일의 수 x 3 + N-4번째에 올 수 있는 타일의 수 x 2 + N-6번째에 올 수 있는 타일의 수 x 2 + ... + 0번째에 올 수 있는 타일의 수 x 2 이다.

2. 0번째에 올 수 있는 타일의 수는 사실 0부터 ~ N까지에 걸친 경우라고 생각할 수 있다. 경우의 수를 N-4부터는 2가지로 고정이 되기 때문에 0번째에 올 수 있는 타일이라는건 0부터 N까지를 모두 채우는 타일의 경우 한가지를 의미하고, 위아래를 뒤집어서 한가지 경우가 더 나오기 때문에 0번째에 올 수 있는 타일도 결국 2가지가 존재한다. 따라서, d[0]에 1을 넣어줘야 for문으로 곱하기 2를 하며 더해줄 수 있다.

3. N-2번째는 3가지 경우가 존재하므로 for문을 마치고 나와서 한번 더 더해준다.

Code