백준 2193. 이친수

 

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

2193번: 이친수

 

d[n] : n 자리로 구성할 수 있는 총 이친 수의 개수

 

일단 이친수의 조건은

 

1. 0으로 시작하지 않는다

2. 1이 두번 연속으로 나타나지 않는다.

 

이 두 조건중 2번째 조건이 중요하다. 

 

d[n]이 n 자리로 구성할 수 있는 총 이친수의 개수이다.

여기서 n번째 자리에는 0또는 1이 올 수 있고 이 두 가지 경우의 수를 합친 것이 d[n]이라고 볼 수 있다.

 

- n번째 자리가 0으로 끝나는 경우

n번째 자리가 0이면 그 전자리 즉 n-1번째 자리가 0이 오든 1이 오든 조건에 위배되지 않는다.

n-1번째 자리에서 0 또는 1로 끝나는 이친수의 개수는 d[n-1]이다. 

그래서 n번째 자리가 0으로 끝나는 경우에는 d[n-1] 만큼 이친수를 구성할 수 있다.

 

- n번째 자리가 1로 끝나는 경우

n번째 자리가 1로 끝나는 경우에는 이친수의 두 번째 조건에 의해 n-1번째 자리에 1이 올 수가없고 0만 올수가 있다.

따라서 n-1번째 자리는 0으로 고정이 되고 n-2번째 자리를 봐야 한다.

n-1번째 자리는 0이므로 n-2번째 자리는 0 또는 1이 둘 다 올 수 있고 이때 이친수의 개수는 d[n-2]이다.

즉 n번째 자리가 1로 끝나는 경우 d[n-2]만큼 이친수를 구성할 수 있다. 

 

위의 두 가지 경우를 합친 것이 d[n]이라고 할 수 있으므로 

d[n] = d[n-1] + d[n-2]

 

코드

arr = [0] * 91
    # 피보나치와 동일

def dp(a):
    if a <= 2:  # base
        return 1

    if arr[a] > 0:
        return arr[a]

    arr[a] = dp(a - 2) + dp(a - 1)
    return arr[a]


n = int(input())  # input

for i in range(n + 1):
    arr[i] = dp(i)

print(arr[n])

 

---

Solution

 

코드를 bottom-up 방식으로

d = [0] * 91
d[1] = 1
d[2] = 1

n = int(input())

for i in range(3, n+1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

 

그리고 배열을 2차원으로 풀 수도 있다.

 

d[n][0] : n자리 이친수중 끝이 0으로 끝나는 수의 개수

d[n][1] : n자리 이친수중 끝이 1로 끝나는 수의 개수

 

최종적으로 구하는 값은 d[n][0] + d[n][1]

 

n자리에서 0으로 끝나는 이친수는 n-1자리에서 0으로 끝나도 되고 1로 끝나도 된다.

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

 

n자리에서 1로 끝나는 이친수는 n-1자리에서 0으로만 끝나야 한다.

d[n][1] = d[n-1][0]

 

d = [[0] * 2 for i in range(91)]  # 91 x 2

d[1][0] = 0
d[1][1] = 1

n = int(input())
for i in range(2, n+1):
    d[i][1] = d[i-1][0]
    d[i][0] = d[i-1][1] + d[i-1][0]
    
print(d[n][0] + d[n][1])

 

파이썬에서 2차원 배열 선언

d = [[0] * 2 for i in range(91)]  # 91 x 2

91 x 2 배열 만들어짐.