[ 백준 - 2193 ] 이친수

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

2193번: 이친수

문제에 대한 설명은 쉽게 이해 되었지만 접근 방식에 대해서는 쉽게 와닿지 않아서 고민 많이 했다.

고민 하는 것 보다 직접 쓰는게 시간이 덜 아까워서 쓰다 보니까 어느정도 감은 잡았다.

질문 게시판을 통해서 힌트도 접했고 풀이 방법이 한개가 아니였다는걸 알게 되었다.

---

[ 📌 풀이 ]

• N의 값이 올라갈 때 마다 2가지의 고려 사항이 생긴다
  • 1의 자리가 0
    
    • 뒤에 0 혹은 1이 와도 이친수가 될 수 있다
  • 1의 자리가 1
    • 뒤에 1이 오면 이친수가 될 수 없다 (= 이전 이친수의 일의 자리가 0인 경우의 수랑 같다)
    • 뒤에 0이 오면 이친수가 될 수 있다

위 조건을 기반으로 식을 만들면

dp[0][n] = dp[0][n - 1] + dp[1][n - 1]
dp[1][n] = dp[0][n - 1]

일의 자리가 0 = 이전 이친수의 두 조건의 경우의수의 합 ===> 이건 논리적인 이유가 없어서 아쉽다(내가) 그냥 노트에 적다가...
일의 자리가 1 = 이전 이친수의 일의 자리가 0인 경우의 수

[ 경우의 수를 직접 구했다 ]

---

[ 📌 코드 - Python(1) ]

### DP expression
N = int(input())

dp = [[0] * (N + 1) for _ in range(2)]
dp[0][0], dp[0][1] = 0, 1
dp[1][0], dp[1][1] = 1, 0

for n in range(2, N + 1):
  dp[0][n] = dp[0][n - 1] + dp[1][n - 1]
  dp[1][n] = dp[0][n - 1]

print(dp[0][N - 1] + dp[1][N - 1])

 

[ 📌 코드 - Python(2) ]

일의 자리의 수의 합을 보면 피보나치 수와 같은 특징을 갖기 때문에 피보나치 수열을 구하는 식과 동일하게 풀린다

### Fibonacci sequence
N = int(input())
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1

def sol(n):
  if dp[n] != 0:
    return dp[n]

  if n == 1:
    return 1
  
  dp[n] = sol(n - 1) + sol(n - 2)
  return dp[n]

print(sol(N - 1))

---

[ 📌 결과 - Python  ]

[ Result - Python ]