사용자 도구

사이트 도구


ps:problems:boj:15717

떡파이어

ps
링크acmicpc.net/…
출처BOJ
문제 번호15717
문제명떡파이어
레벨골드 5
분류

애드혹

시간복잡도O(logn)
인풋사이즈n<=10^12
사용한 언어Python
제출기록28776KB / 68ms
최고기록56ms
해결날짜2021/02/04

풀이

  • 식만 잘 정리하면 된다.
  • 간단하게 재귀형태로 정리하면, 떡 n개를 며칠동안 나눠먹는 방법 f(n)은 {첫째날에 1개를 먹는 경우} + {첫째날에 2개를 먹는 경우} + … + {첫째날에 n개를 먹는 경우} 로 나눌수 있다. 첫째날에 k개를 먹는 경우는 나머지 날 동안 n-k를 나눠먹는 방법 f(n-k)이므로. f(n) = f(n-1) + f(n-2) +… + f(1) = f(n-1) + f(n-1) = 2*f(n-1). 단순한 등비수열이고, f(1)=1 이므로 f(n)=2^n. 이제 코딩은 1줄에도 끝낼수 있다..
  • n=0 일때 0을 출력하는 것에만 주의.

코드

"""Solution code for "BOJ 15717. 떡파이어".

- Problem link: https://www.acmicpc.net/problem/15717
- Solution link: http://www.teferi.net/ps/problems/boj/15717
"""

MOD = 10**9 + 7


def main():
    N = int(input())
    print(pow(2, N - 1, MOD) if N > 0 else 1)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
D​ B P U M
 
ps/problems/boj/15717.txt · 마지막으로 수정됨: 2021/07/31 15:50 저자 teferi