ps:problems:boj:15311
약 팔기
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 15311 |
문제명 | 약 팔기 |
레벨 | 플래티넘 5 |
분류 |
애드혹 |
시간복잡도 | O(1) |
사용한 언어 | Python 3.13 |
제출기록 | 32412KB / 32ms |
최고기록 | 28ms |
해결날짜 | 2025/04/07 |
풀이
- 약봉지에 전부 1개씩 채우면 1~N까지의 모든 수를 만들수 있다.
- 약봉지에 전부 2개씩 담으면 2~2까지의 모든 짝수를 만들수 있다. 그러면, 맨 왼쪽의 약봉지에만 1개를 담고, 나머지 (K-1)개의 약봉지는 2개를 담으면? 1부터 2K-1까지의 모든 수를 만들수 있다.
- 이것을 확장해보자. 왼쪽 x개에는 1개씩 담고, 오른쪽 (K-x)개는 x+1개씩 담으면, 1부터 (K-x)*(x+1)+x 까지의 모든 수를 만들수 있다.
- K=2000, x=1000 으로 잡으면 1~1001001 개를 만들수 있으므로 문제의 조건을 만족한다
코드
"""Solution code for "BOJ 15311. 약 팔기".
- Problem link: https://www.acmicpc.net/problem/15311
- Solution link: http://www.teferi.net/ps/problems/boj/15311
Tags: [ad hoc]
"""
def main():
N = int(input()) # pylint: disable=unused-variable
print(2000)
print('1000 ' * 1000, '1 ' * 1000)
if __name__ == '__main__':
main()
ps/problems/boj/15311.txt · 마지막으로 수정됨: 2025/04/07 08:27 저자 teferi
토론