ps:problems:boj:14437
목차
준오는 심술쟁이!!
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 14437 |
| 문제명 | 준오는 심술쟁이!! |
| 레벨 | 골드 3 |
| 분류 |
조합론 |
| 시간복잡도 | O(n+k) |
| 인풋사이즈 | n<=3000, k<=3000 |
| 사용한 언어 | Python 3.13 |
| 제출기록 | 32412KB / 32ms |
| 최고기록 | 32ms |
| 해결날짜 | 2026/04/09 |
풀이
- 바꿔쓰면 0≤x_i≤25 일때, x_1+x_2+..+x_l = s 가 되는 (x_1,…,x_l) 의 개수를 세는 문제이다
- 공식 풀이는 O(s*l) 의 DP이지만, 조합론적 방법으로 O(s+l) 에 해결이 가능하다. 풀이는 상한이 주어진 composition 참고
코드
"""Solution code for "BOJ 14437. 준오는 심술쟁이!!".
- Problem link: https://www.acmicpc.net/problem/14437
- Solution link: http://www.teferi.net/ps/problems/boj/14437
Tags: [combinatorics]
"""
from teflib import combinatorics
MOD = 1_000_000_007
def main():
s = int(input())
problem = input()
print(combinatorics.count_compositions(s, len(problem), MOD, hi=25))
if __name__ == '__main__':
main()- Dependency: teflib.combinatorics.count_compositions
ps/problems/boj/14437.txt · 마지막으로 수정됨: 2026/04/09 10:51 저자 teferi
토론