(15311) 약 팔기

https://www.acmicpc.net/problem/15311

단계별로 풀어보기

37단계(해 구성하기) 9번째

 

 

 

앞쪽 k-1개의 판매대에 약을 1개씩 올려두었다고 생각하자.

이러면 k-1개의 판매대에서 구간 [1,k-1]에 해당하는 약을 줄 수 있다.

k번째 판매대에 약을 k개 올려두면, k개를 집고 1개씩 놓인 약을 추가로 집어 구간 [k,2k-1]에 해당하는 약을 줄 수 있다.

k+1번째 판매대에도 약을 k개 올려두면 k+k개를 집고 1개씩 놓인 약을 추가로 집어 구간 [2k,3k-1]에 해당하는 약을 줄 수 있다.

판매대는 최대 2000개이므로 이렇게 하면 (2000-(k-1))*(k-1)개까지의 약을 전부 줄 수 있다. 이 값은 k=1001일 때 최대이다.

따라서 1~1000번째 매대에 약을 1개씩 ,1001~2000번째 메대에 약을 1001개씩 놓으면 약을 1,000,200개까지 줄 수 있으므로 문제의 조건 내에서 해결이 가능하다.

 

N의 범위에 맞춰 계산해 출력할 수도 있지만 어차피 최소 조건은 없으므로 그냥 입력에 관계없이 항상 가장 많이 줄 수 있는 방식을 출력하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  
  cin >> n;
  
  cout << "2000\n";
  for(int i=1;i<=1000;i++)  cout << 1 << " ";
  for(int i=1;i<=1000;i++)  cout << 1001 << " ";
  
  return 0;
}