[백준] 1904 01타일 Python

1. 문제

00과 1로 이루어진 타일을 붙여 길이가 n인 모든 2진 수열의 개수를 구하고
그 값을 15746로 나눈 나머지를 출력하는 문제 

2. 요구사항

시간 제한 0.75초 

메모리 제한 256MB

1 <= N <= 1,000,000

3. 알고리즘 분류

* 다이나믹 프로그래밍

4. 접근 방식

처음에는 n = 7 까지 모든 경우의 수를 계산해 봤는데, 알고보니 피보나치 수열이었다

그리고 같은조 ㅎㅇ님이랑 얘기하며 알게된 내용인데, 아래와 같은 사실을 알게 되었다

1) 타일은 00 과 1 로 구분할 수 있다

2) 그래서 n == 3 이상일 때

◻️◼️◼️ 한 칸만 비어있는 경우는 빈 칸에 1 이 들어가고 

◻️◻️◼️ 두 칸이 비어있는 경우는 빈 칸에 00 이 들어간다고 생각하면

n == 3 이상 일 때는 n-1 과 n-2 의 합이다

(◻️◼️◼️ / ◼️◼️◻️ 도 모두 n-1 의 경우가 다 포함되니 생각하지 않아도 된다)

결국 재귀로 구현할 수 있다는 말이었지만, N 이 최대 1,000,000 이므로

시간 복잡도를 고려하여 반복문 + 메모이제이션을 통해 구현하려고 노력했다 

5. 코드 구현

첫번째 시도

# 00 과 1 로 이루어진 타일을 붙여 
# 길이가 n 인 모든 2진 수열의 개수를
# 15746 으로 나눈 나머지를 출력하는 문제

def fibo(n):
    if n <= 1: # 기저 설정 
        return n
    list = [0] * (n+1)
    list[1] = 1

    # 메모이제이션 
    for i in range(2, n+1):
        list[i] = list[i-1] + list[i-2]    
    result = list[n] 
    return result

if __name__ == '__main__':
    n = int(input())
    tile = fibo(n)
    tile_result = tile % 15746
    print(tile_result)

 

두번째 시도

그래서 for 문에서 list[i] 를 돌릴 때 계산한 값에서 15746 을 나눈 값을 list 에 넣어줬다 

근데 틀렸습니다 가 나왔다, 답은 맞는데 왜 틀렸다고 하지?

# 00 과 1 로 이루어진 타일을 붙여 
# 길이가 n 인 모든 2진 수열의 개수를
# 15746 으로 나눈 나머지를 출력하는 문제

def fibo(n):
    if n <= 1: # 기저 설정 
        return n
    list = [0] * (n+1)
    list[1] = 1

    # 메모이제이션 
    for i in range(2, n+1):
        list[i] = (list[i-1] + list[i-2]) % 15746
    result = list[n]
    return result

if __name__ == '__main__':
    n = int(input())
    tile = fibo(n)

    print(tile)

 

세번째 시도

완전 피보나치가 아니고 n = 1 일 때 1, n = 2 일 때 2, n = 3 일 때 3 이렇게 올라가서

초기값을 다르게 줘야 한다는 사실을 깨달았다, 그래서 list[0] = list[1] = 1 로 설정했다 

그리고 방금 ㅇㅈ님에게 힌트를 얻었는데 '모듈러 연산' 을 사용했다고 한다 

모듈러 연산은 다음에 공부해봐야겠다 

# 00 과 1 로 이루어진 타일을 붙여 
# 길이가 n 인 모든 2진 수열의 개수를
# 15746 으로 나눈 나머지를 출력하는 문제

def fibo(n):
    if n <= 1: # 기저 설정 
        return n
    list = [0] * (n+1) 
    list[0] = list[1] = 1

    # 메모이제이션 
    # for 문 안에서 나머지를 저장하여 성능 저하 방지 
    for i in range(2, n+1):
        list[i] = (list[i-1] + list[i-2]) % 15746
    # result = list[n]
    # return result
    return list[i]

if __name__ == '__main__':
    n = int(input())
    tile = fibo(n)

    print(tile)