사용자 도구

사이트 도구


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