타일

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

중복을 고려하지 않고

• d[i]
  • d[i-2] * 2 + d[i-1]

중복을 고려하여

• 전체 타일 수 = A + 2B

  • A : 중복되지 않는 수
  • B : 중복되는 수

• 중복을 제거한 타일 수 = A + B = (A + 2B + A) / 2

• A 개수 구하기

  • i가 홀수인 경우

    • 가운데 2*1을 두고, 남은 좌우 채움
    • s[i] = d[i/2]

  • i가 짝수인 경우

    • s[i] = d[i/2-1] * 2 + d[i/2]
    • 가운데, 1*2를 주고, 남은 좌우 채움
      • d[i/2-1]
    • 가운데, 2*2를 주고, 남은 좌우 채움
      • d[i/2-1]
    • 반반 나눠서 채움
      • d[i/2]

결과

• 런타임 에러가 뜸

• 해결 : 배열 31로 고정