[백준 온라인 저지] 01타일

문제 

• https://www.acmicpc.net/problem/1904

01타일 - 클릭시 문제 사이트로 넘어갑니다.

 

나만의 풀이

• 00, 1 타일을 사용하여 수열을 생성하기 때문에 N = 1부터 케이스를 따져봤다.
  
  • N = 1이면, 1 으로 총 1개의 2진 수열을 만들 수 있다.
  • N = 2이면, 11, 00 으로 총 2개의 2진 수열을 만들 수 있다.
  • N = 3이면, 111. 001. 100 으로 총 3개의 2진 수열을 만들 수 있다.
  • N = 4이면, 1111, 0011, 0000, 1001, 1100 으로 총 5개의 2진 수열을 만들 수 있다.
  • 위의 규칙에서 N = 3까지 보면, N = 2 11, 00 에서 추가되는 건 1 밖에 없기 때문에 N = 3은 N = 2 + N = 1로 생각해볼 수 있었다.
  • 위의 규칙을 일반화 하였을 때, function(N) = function(N - 1) + function(N - 2) 로 정의할 수 있어 피보나치와 같이 풀어보았다.

 

첫번째 코드

def dp(N):
    
    if N <= 2:
        return N
    else:
        return dp(N - 1) + dp(N - 2)

N = int(input())

print(dp(N) % 15746)

• 피보나치 수열을 푸는 방법과 동일하게 코드를 작성하여 제출하였다.
• 위의 코드를 제출하면 메모리 에러가 발생한다.
• N이 커지면 값도 커지기 때문에 메모리 초과가 발생했다고 추측했다. (그래서 마지막에 15746으로 나눴을지도)

 

두번째 코드

n = int(input())

dp = [0] *  1000001
dp[1] = 1
dp[2] = 2

for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
    
print(dp[n])

• 재귀로 풀지 않고 반복문으로 풀었으며, N의 최대 길이만큼 리스트를 생성하여 값을 채워나가는 식으로 변경

 

 

Github : https://github.com/Limseunghyun95/code_test/blob/master/baekjoon/p_1904.py