날짜: 2021년 10월 7일
소요 시간: 25분 26초
카테고리: 수학
태그: gold.5, 15717, 파이썬

백준 15717 - 떡파이어

입출력 예시

내가 적은 코드 1

import sys
from itertools import product

N = int(sys.stdin.readline().strip())
count = 0

for check, i in enumerate(range(N, 0, -1)):
    for j in product(range(1, check+2), repeat=i):
        if sum(j) == N:
            count += 1
            print(j)

print((count)%(10**9+7))

길이가 1 부터 N까지 합이 N이 되는 중복 순열의 개수를 구하는 식 -> 메모리 초과

내가 적은 코드 2

import sys

N = int(sys.stdin.readline().strip())

if N == 0:
    print(1)
else:
    print((2**(N-1))%(10**9+7))

답이 2의 N-1승이 된다는 규칙을 찾았지만 -> 메모리 초과

풀이 과정

1. 길이가 1 부터 N까지 합이 N이 되는 중복 순열의 개수를 구하는 식이라는 패턴을 찾았지만
   10의 12승이라는 입력을 버텨내지 못하고 메모리 초과

2. 2의 N-1승이 출력된다는 규칙을 찾았고
   파이썬은 이론적으로 정수형의 오버헤드가 일어나지 않는다고 알고 있어서 10의 12승이 들어와도 괜찮을거라 생각했지만
   BOJ 자체의 메모리 리미트로 메모리 초과

3. 베스트 코드
   파이썬의 ** 연산식과 파이썬 내장 함수인 pow()는 같은 역할을 수행하고 인자의 크기가 작을 때는 상관이 없지만
   인자의 크기가 커지면 pow()가 시간적으로나 메모리적으로나 효율적인 수행을 한다고 함

베스트 코드

import sys

n = int(sys.stdin.readline().strip())

if n == 0:
    print(1)
else:
    print(pow(2,n-1,10**9+7))

반성

• pow()라는 파이썬 내장함수를 새로 알게 되었다.