https://www.acmicpc.net/problem/15311
| 시간 제한 | 메모리 제한 |
| 1초 | 512MB |
문제
약장수 강욱이는 오늘도 약을 판다. 짬에서 나오는 Vibe로 화려한 언변을 구사하는 강욱이는 최고의 약장수이다. 하지만 이런 그에게도 고민거리가 하나 있으니...
동규라는 단골 손님이 있는데, 그는 매일 약을 1알에서 100만알 사이의 랜덤한 자연수 개수만큼 원했다. 주문을 받은 강욱이는 약 상자에서 한 알씩 약을 세서 꺼내주곤 했는데, 그것이 답답했던 동규는 강욱이에게 매번 화를 냈던 것이다.
이러다 동규가 자기를 때리지 않을까 무서웠던 강욱이는 동규가 원하는 만큼의 약을 빨리 건네주기 위한 방법을 고민하기 시작했다. 그는 곧 소싯적에 공부했던 Algorithm을 이용해 다음과 같은 방법을 생각해 냈다.
'약 봉지 여러 개에 각각 적절한 수의 알약을 담아서 일렬로 늘어 놓은 뒤, 동규가 약을 k알 달라고 하면 총 k알의 약이 들어있는 어떤 연속한 구간의 약 봉지들을 한 번에 집어 주면 되겠군!'
아쉽게도, 강욱이의 약 판매대는 봉지를 일렬로 최대 2000개까지만 올려놓을 수 있다. 강욱이는 적은 수의 봉지에 알약을 적절히 담아서 동규가 100만 이하의 어떤 수를 부르든 그 수에 해당하는 만큼의 약을 줄 수 있었으면 한다. 하지만 물리 공부를 하느라 Algorithm 공부를 열심히 하지 못한 강욱이는 어떻게 할지 몰라 쩔쩔매고 있다. 강욱이를 도와주자!
입력
첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N (=1,000,000) 이 주어진다.
출력
첫 번째 줄에는 필요한 약봉지의 개수 K (1 ≤ K ≤ 2,000) 를 출력한다.
두 번째 줄에는 왼쪽부터 순서대로 각 약봉지에 들어있어야 하는 약의 수를 출력한다. 각 봉지에는 1알 이상 100만알 이하의 약이 있어야 한다.
풀이
한 줄로 이어진 약 봉지의 연속된 구간으로 1~N알의 약을 모두 구성할 수 있어야 합니다. 만약 k개의 약 봉지에 모두 약을 1개씩 넣는다면 1~k개 까지의 약을 구성할 수 있습니다.
문제에서는 약 봉지의 개수는 최대 2,000개라고 합니다. 이 방법으로는 최대 2,000알의 약을 구성할 수 있습니다. 하지만 입력 조건에서 동규의 최대 약 요구량은 1,000,000개라고 되어있습니다. 한참 모자라네요.
우리가 사용하는 10진법을 생각해봅시다. 10진법은 위치적 기수법으로 1의 자리에서 5가 있다면 5이지만 10의 자리에 똑같은 5가 있다면 50입니다. 약 봉지도 하나의 약 봉지가 약 1알이 들어있을 수도, 10알이 들어있을 수도 있습니다. 그렇다면 위의 그림에서 5개만 1알짜리 약 봉지로 만들고 남은 1개를 6알짜리 약 봉지로 만든다면 어떨까요?
이제 1~11개 까지의 약을 구성할 수 있게 되었습니다. 1의 개수를 줄여봅시다.
이렇게 하면 1~14개 까지의 약을 구성할 수 있네요.
이제 1~15개 까지 구성됩니다.
이렇게 하면 다시 줄어들어서 1~14개 까지 구성할 수 있네요. 절반의 약 봉지만 여러 개의 약을 넣어야 할 것 같습니다.
그럼 2,000개의 약 봉지 중에서 절반인 1,000개의 약 봉지에 약을 1알씩 넣으면 1,001개의 약은 한 봉지에 담아버리면 됩니다. 이렇게 1 * 1,000 + 1001 * 1,000 = 1,002,000개의 약을 구성할 수 있습니다.
[심화 문제: 백준 19568 직사각형]
https://www.acmicpc.net/problem/19568
정답 코드
n = int(input())
print(2000)
print(*[1]*1000+[1001]*1000)
