[백준] 15311번(python 파이썬) - 약 팔기

문제 링크: https://www.acmicpc.net/problem/15311

15311번: 약 팔기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	1230	638	513	51.558%

문제

약장수 강욱이는 오늘도 약을 판다. 짬에서 나오는 Vibe로 화려한 언변을 구사하는 강욱이는 최고의 약장수이다. 하지만 이런 그에게도 고민거리가 하나 있으니...

동규라는 단골 손님이 있는데, 그는 매일 약을 1알에서 100만알 사이의 랜덤한 자연수 개수만큼 원했다. 주문을 받은 강욱이는 약 상자에서 한 알씩 약을 세서 꺼내주곤 했는데, 그것이 답답했던 동규는 강욱이에게 매번 화를 냈던 것이다.

이러다 동규가 자기를 때리지 않을까 무서웠던 강욱이는 동규가 원하는 만큼의 약을 빨리 건네주기 위한 방법을 고민하기 시작했다. 그는 곧 소싯적에 공부했던 Algorithm을 이용해 다음과 같은 방법을 생각해 냈다.

'약 봉지 여러 개에 각각 적절한 수의 알약을 담아서 일렬로 늘어 놓은 뒤, 동규가 약을 k알 달라고 하면 총 k알의 약이 들어있는 어떤 연속한 구간의 약 봉지들을 한 번에 집어 주면 되겠군!'

아쉽게도, 강욱이의 약 판매대는 봉지를 일렬로 최대 2000개까지만 올려놓을 수 있다. 강욱이는 적은 수의 봉지에 알약을 적절히 담아서 동규가 100만 이하의 어떤 수를 부르든 그 수에 해당하는 만큼의 약을 줄 수 있었으면 한다. 하지만 물리 공부를 하느라 Algorithm 공부를 열심히 하지 못한 강욱이는 어떻게 할지 몰라 쩔쩔매고 있다. 강욱이를 도와주자!

입력

첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N (=1000000$=1\, 000\, 000$) 이 주어진다.

출력

첫 번째 줄에는 필요한 약봉지의 개수 K (1≤ K ≤2000) 를 출력한다.

두 번째 줄에는 왼쪽부터 순서대로 각 약봉지에 들어있어야 하는 약의 수를 출력한다. 각 봉지에는 1알 이상 100만알 이하의 약이 있어야 한다.

 

 

 

 

 

 

풀이

---

이 문제는 처음에 봤을 때 문제가 무슨소리를 하는건지 이해가 가지 않았다.

 

한 10번정도 천천히 읽어보니까 이해가 갔다. ㅋㅋ

 

우선 문제를 해석해보자.

 

1. n(주문할 수 있는 최대 약의 개수)를 받고 약봉지를 먼저 배열한다. (최대 2000봉지 가능)

 

2. n이하의 약을 주문받고 연속된 약봉지를 집었을 때 n이하의 주문에 대해서 전부 출력이 가능해야 한다.

 

 

문제에 나온 예시를 봤는데 이게 대체 무슨 원리로 출력이 나오는지 잘 모르겠다. 

일단 6이하의 수에 대해서 연속된 구간으로 약봉지를 뽑았을 때 모두 가능하다는 것은 알아냈다.

 

그래서 나는 만약 n이 7이라면 어떻게 될까? 라는 생각을 해봤다.

7 -> 1 3 2 1 이면 되지 않을까...? (n == 6일때에서 1만 붙였다)

8 -> 1 3 2 1 1

9 -> 1 3 2 1 1 1 

 

여기서 나의 사고의 흐름은 다음과 같았다.

근데 왜 n == 6일때 1 1 1 1 1 1은 안될까...?

사실 문제의 답이 여러개가 아닌가라는 생각을 했다. 

그래서 일단 시도해보기로 했다.

1로 1000000을 만들수는 없으니 생각을 좀 더 해봤다 ( 약봉지 2000개 제한)

-> 1로 만들 수 있는 수들을 넣어놓는다면 어떨까...?

나는 이러한 생각을 하고 숫자에서 영감을 받았다. 1000000/2000 = 500

근데 1로 만들 수 있는 수 최대 2000개

1과 나머지 숫자의 밸런스를 맞춰봤더니 1과 1000이 나왔다.

 

1 이 1000개 1000이 999개 있으면 이론상 전부 구현이 가능하다는 것을 알아냄

1999는

1, 999개에다가 1000하나출력

나머지도 마찬가지였다. 

 

이 생각을 한 후 코드짜는데는 5분정도 걸린 것 같다.

근데 예시출력과 달라서 이게 될까...? 싶었는데 이게 정답처리가 되버려서 신기했다.

 

예시를 좀 여러개 만들어주지.. 생각하느라 좀 고생했다.

 

암튼 오늘은 여기까지

 

구현 코드

---

from sys import stdin
input = stdin.readline

n = int(input())

if n >= 1000:
    tmp_1 = n%1000
    tmp_2 = n // 1000
    if tmp_2 == 1000: # 백만일 경우 1000을 1000개 출력할수는 없으므로 따로처리
        print(1999)
        for _ in range(1000):
            print(1, end=' ')
        for _ in range(999):
            print(1000, end=' ')
        exit(0) # 처리후 코드 종료
    print(tmp_1+tmp_2) # 백만이하라면 1000으로 나눈 나머지와 1000으로 나눈 몫을 출력
    for _ in range(tmp_1):
        print(1, end=' ')
    for _ in range(tmp_2):
        print(1000, end=' ')
    print()
else:
    print(n) # 1000이하라면 그냥 1로 만들 수 있으므로 1 을 n개출력
    for _ in range(n):
        print(1, end=' ')
    print()