[Python] BOJ 1904 : 01타일

요구사항

1. 시간 제한 0.75
   1. N이 최대 1,000,000 이기 때문에 O(NlogN) 까지 가능할 거 같다. 
2. 메모리 제한 256MB - 충분
3. N이 주어졌을 때 가능한 모든 경우의 수를 카운트.
4. 모든 경우의 수 // 15746으로 나눈 나머지를 출력 

설계

1. 피보나치 수열 확장판이다. 
2. N = 1일 때, 1
3. N = 2일 때, 2
4. N = 3일 때, 3
5. N =4 일 때, 5
6. 따라서 bottom-up 방식으로 구현한다. 
7. 사용자로부터 입력을 받는다. 
8. dp테이블을 초기화해준다. 
   1. 총 들어오는 입력값 + 1 만큼
9. 초기값 dp[1]과 dp[2]를 설정해준다.
   • dp[2]의 경우는 if N > 1: 일 때 dp[2] = 2로 예외처리를 해주어야 한다.

# if N > 1: 없는 경우
N = int(input())  # N = 1
dp = [0] * (N + 1)  # dp = [0, 0]
dp[1] = 1
dp[2] = 2  # 오류 발생! dp[2]는 존재하지 않음 (IndexError)

• if N >1: 있는 경우

N = int(input())  # N = 1
dp = [0] * (N + 1)  # dp = [0, 0]
dp[1] = 1
if N > 1:  # N이 1보다 클 때만 실행
    dp[2] = 2  # 이 코드는 실행되지 않음

 

구현

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

# 초기 값 설정
dp[1] = 1
if N > 1:
    dp[2] = 2

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

print(dp[N])

초기 생각 흐름...

N = 1 일 때 (1) 
N = 2  (2)
00, 11

N = 3 
001, 100, 111 (3)

N = 4
0000, 0011, 1100, 1111, 1001 (5) 

N = 5
00001, 00011, 00110, 00111, 11100, 11100, 11111, 10000 (8)

DP 란 어떠한 문제를 작은 문제의 연장선이라고 생각하는 것. 
어떤 수를 나누었을 때, 0의 개수가 2로 나누어 떨어지면 되는 거
모든 조합을 뿌려 놓고 거기서 0이랑 나누어 떨어지는 것만 고르면 안되나?
그럼 조합을 어떻게 뿌리지? 
브루트포스 알고리즘을 사용? 
근데 다 볼 필요는 없는 데 방법을 모르겠다. 

N 이 들어올 때마다. 그 카운터 값을 저장.

피보나치나 풀고싶다..
? 
개꿀

 

+ 2024.10.02 다시 풀어보기 

import sys
input = lambda: sys.stdin.readline().rstrip()

def tile(num):
    dp = [0] * (num + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3,num + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[num]

def main():
    N = int(input())
    print(tile(N))

if __name__ == "__main__":
    main()

• 메모리 초과 났다..
• Bottom-Up(상향식)의 경우 모든 가능성을 저장하여 반복된 계산은 가져다 쓸 수 있어 시간 복잡도 측면에서는 효율이 좋지만, 모든 가능성을 DP테이블에 저장하기 때문에 메모리 초과가 났을 거 같다. 
• Top-Down(하향식)의 경우 계산에 사용될 계산만 저장하니 하향식 방법을 사용해야겠다. 

import sys
input = lambda: sys.stdin.readline().rstrip()

def tile(num, dp):
    if dp[num] != 0:
        return dp[num]

    if num == 1:
        return 1
    if num == 2:
        return 2

    dp[num] = tile(num - 1, dp) + tile(num - 2, dp)
    return dp[num]

def main():
    N = int(input())
    dp = [0] * (N+1)
    print(tile(N, dp))

if __name__ == "__main__":
    main()

• 런타임에러(RecursionError) 가 나왔다. 재귀의 깊이를 설정해줘야 될 듯하다.
• 설정해주어도 메모리 초과난다. 깊이를 10**7 -> 10**6 으로 했더니 시간초과 나온다. 
• 아 그리고 % 15746을 계속 빼먹고 있었다. 그래서 메모리 초과가 계속 났나..?

%15746 연산과 N > 1클 때 dp[2] = 2 해주면 성공할 수 있다. 

 

상향식 버전

import sys
input = lambda: sys.stdin.readline().rstrip()

def tile(num):
    dp = [0] * (num + 1)
    dp[1] = 1
    if num > 1:
        dp[2] = 2
    
    for i in range(3,num + 1):
        dp[i] = (dp[i-1] + dp[i-2]) % 15746
    
    return dp[num]

def main():
    N = int(input())
    print(tile(N))

if __name__ == "__main__":
    main()