ps:problems:boj:18291
목차
비요뜨의 징검다리 건너기
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 18291 |
| 문제명 | 비요뜨의 징검다리 건너기 |
| 레벨 | 골드 5 |
| 분류 |
조합론 |
| 시간복잡도 | O(T*logn) |
| 인풋사이즈 | T<=1000, n<=10^9 |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 31256KB / 48ms |
| 최고기록 | 44ms |
| 해결날짜 | 2023/02/13 |
풀이
- 1번과 N번 사이에 있는 징검다리를 원하는 만큼 밟고 갈수 있다.
- 따라서 {2, … ,N-1}의 부분집합의 갯수를 구하는 문제가 된다. 답은 2^(N-2) % MOD. 거듭제곱의 빠른 계산 (Exponentiation by squaring)을 이용하면 O(logN)에 구할수 있다.
- N=1일때에는 1을 출력하는 것만 신경써주면 된다
코드
"""Solution code for "BOJ 18291. 비요뜨의 징검다리 건너기".
- Problem link: https://www.acmicpc.net/problem/18291
- Solution link: http://www.teferi.net/ps/problems/boj/18291
"""
import sys
MOD = 10**9 + 7
def main():
T = int(sys.stdin.readline())
for _ in range(T):
N = int(sys.stdin.readline())
print(1 if N == 1 else pow(2, N - 2, MOD))
if __name__ == '__main__':
main()ps/problems/boj/18291.txt · 마지막으로 수정됨: 2023/02/13 08:16 저자 teferi
토론