[C++] 백준 2193번 풀이 (이친수)

- 문제 (2193번) : 이친수

• 링크 : https://www.acmicpc.net/problem/2193

• 자리수 N이 주어졌을 때 N자리 이친수의 개수 출력

---

- 입력 및 출력

[입력]

• 첫째줄에 자리수 N 입력

[출력]

• N자리 이친수의 개수 출력

---

- 문제 풀이

• N자리수의 이친수는 다음과 같이 2가지 경우로 만들 수 있음.

  1. 마지막이 0으로 끝날 때
     • 1xxxxx...xxxx0 이 될 수 있고, N-1번째 수는 0 또는 1이 모두 올 수 있음.
     • 따라서 마지막이 0으로 끝나는 경우는 N-1자리수까지의 이친수의 개수와 동일
       (마지막을 0으로 고정시키면 선택해야하는 자릿수는 N-1개)

  2. 마지막이 1로 끝날때
     • 1이 연달아오는 "11" 문자열은 존재할 수 없으므로 끝이 01로 끝나는 이친수를 선택하면 됨.
     • 따라서 마지막이 1로 끝나는 경우는 N-2자리수까지의 이친수의 개수와 동일
       (마지막을 01로 고정시키면 선택해야하는 자릿수는 N-2개)

• 따라서 memoization을 활용해 값을 저장하면
  ( N자리 이친수의 개수 : arr[N] )

  arr[N] = arr[N-1] + arr[N-2]

  이 된다.
  ( 두개를 더하는 이유는 2가지 경우의 수 모두를 생각하므로 )
  

---

- 최종 코드