[백준 2193] 이친수

이친수(2193)

문제 출처 : https://www.acmicpc.net/problem/2193

 

0과 1로 이루어진 이진수 중 특별한 성질을 가지고 있는 이친수를 찾는 문제 입니다. 이친수의 성질은 다음과 같이 두 가지 입니다.

1. 이친수는 1로 시작합니다.
2. 이친수는 1이 연속해서 나타나지 않습니다.

이 두 가지 성질을 만족하는 이친수의 개수를 찾는 것 입니다.

문제를 보면 DP의 Top-Down으로 문제를 해결할 수 있을것 같습니다. 함수를 만들고 그 함수의 특징을 다음과 같이 정의 하였습니다.

solve(n, c)

n은 이친수의 길이 입니다. 그리고 c는 마지막 숫자를 나타냅니다. 즉 0 아니면 1이 됩니다. 그리고 이 함수의 리턴값은 길이가 n까지이고 마지막 숫자가 c인 이친수의 경우의 수 입니다.

코드 작성하기

그럼 코드를 작성해 보겠습니다.

입력 받기

N = int(input())

이친수의 길이 N을 입력으로 받습니다.

Top-Down 1

뼈대가 되는 로직을 만들어 보겠습니다.

def solve(n, c):
    ans = solve(n - 1, 0)
    if c == 0:
        ans += solve(n - 1, 1)

    return ans
    
print(solve(N, 0) + solve(N, 1))

길이 n까지의 이친수의 경우의 수는 다음과 같습니다.

1. n - 1 길이의 0으로 끝나는 이친수
2. n - 1 길이의 1로 끝나는 이친수

이 두가지의 합과 같습니다. 따라서 전체의 경우는 0으로 끝나는 경우와 1로 끝나는 경우의 합으로 구해줍니다.

먼저 길이가 n - 1이고 0으로 끝나는 이친수를 ans에 더해줍니다. 다음으로 마지막 숫자가 0인 경우에만 1로 끝나는 이친수를 더해줍니다. 왜냐하면 1이 연속으로 나올 수 없기 때문 입니다.

마지막으로 길이가 N이면서 끝이 0인 경우와 1인 경우를 더해주면 전체 경우의 수를 알 수 있습니다.

Top-Down 2

앞 선 로직은 뼈대만 있는 알고리즘입니다. 여기에 종료조건과 메모이제이션을 추가해 주겠습니다.

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

def solve(n, c):
    if n == 1: 
        if c == 1:
            return 1     
        return 0

    if dp[n][c]:
        return dp[n][c]

    ans = solve(n - 1, 0)
    if c == 0:
        ans += solve(n - 1, 1)
    
    dp[n][c] = ans
    return ans

print(solve(N, 0) + solve(N, 1)) 

먼저 종료 조건입니다. 종료 조건은 이친수의 길이가 1일때 입니다. 길이가 1인 경우 끝값인 c에 따라 달라집니다. 첫 번째 숫자는 무조건 1로 시작하기 때문에 c 가 1인 경우에만 1을 리턴합니다. 0인 경우는 이친수가 될 수 없기 때문에 0을 리턴합니다.

다음으로 메모이제이션 처리 입니다. dp는 길이 N까지를 가지고 있고 각 길이의 0으로 끝나는 이친수의 경우의 수, 1로 끝나는 이친수의 경우의 수를 저장해 놓습니다. dp[n][c]가 존재하면 그 값을 가져다 쓰고, 없으면 계산하여 마지막에 ans값을 저장해 놓습니다.

이렇게 제출해서 시간초과가 난다면 Bottom-Up으로 만들어볼까 했는데 다행히 통과가 되었습니다. 필요하다면 각자 Bottom-Up으로 변형시켜 보시기 바랍니다.