백준 1904번 문제 바로가기

조합(combinations)을 이용한 풀이 (시간초과)

# 입력
import sys
import math
n = int(sys.stdin.readline())
ans = 0

# 처리
for i in range(n//2 + 1):
    ans += math.comb((n-i), i)
    
print(ans)

# N=4
# 4C0 1111
# 3C1 0011, 1001, 1100
# 2C2 0000

dp 풀이

조합으로 풀었더니 시간초과 문제가 발생해서, dp 방식으로 풀어보기로 했다. (참 쉽지 않구만!) 하긴 0.75초의 시간제한이 걸려있는걸 보면 bruteforce는 아니겠구만! 생각이 들긴 하다. 그래서 생각한 것은 dp 방식으로 풀어보자! (길이가 n일 떄의 가짓수) = $ a_{n} $ 이라면, $ a_{n} = a_{n-1} + 2 * a_{n-2} $ 을 만족한다 (n-1에 1을 추가하는 경우) (n-2에 11또는 00을 추가하는 경우)

# 입력
import sys
n = int(sys.stdin.readline())
a,b = 1,0

# 처리
for i in range(n):
    a,b=(a+b)%15746,a

print(a)

여담 메모리 초과 에 관하여…

  1. itertools의 combinations 사용하기 
    from itertools import combinations
len(list(combinations(range(n-i), i)))
  2. math의 comb 사용하기 
    import math
math.comb(n-i,i)

itertools.combinations은 iterable한 요소를 첫 번쨰 파라미터로 받아서 모든 경우의 수를 보여준다. 전달한 값의 요소가 많아질 경우 길이가 길어져 메모리 초과 문제가 발생할 수 있다. 따라서 굳이 모든 경우의 결과값이 불필요한 경우 math.comb을 이용해서 메모리를 아낄 수 있다. (경우의 수만 return함)

참고

n이 1부터 5까지의 test case

# 1

# 00
# 11

# 100
# 001
# 111

# 0000
# 1100
# 0011
# 1001
# 1111

# 00001
# 00111
# 10011
# 11001
# 11100
# 00001
# 00100
# 10000
# 11111