[BOJ 15311 // C++] 약 팔기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15311번 문제인 약 팔기이다.
문제는 아래 링크를 확인하자.

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

15311번: 약 팔기

1을 1000개 나열한 수열의 첫 원소부터 i번째 원소까지의 합은 항상 i가 됨을 관찰하자.

또한, 1000을 1000개 나열한 수열의 첫 원소부터 j번째 원소까지의 합은 항상 1000j가 됨을 관찰하자.

 

이와 같은 두 관찰을 이용하면 위의 두 수열을 이어붙인 수열에서는 1 이상 100만 이하의 모든 수에 대하여 합이 그 수인 연속 부분수열을 어렵지 않게 찾을 수 있음을 알 수 있다. 해당 수열은 문제의 조건을 만족하므로 이를 출력해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << 2000 << '\n';
	for (int i = 0; i < 1000; i++) cout << 1 << ' ';
	for (int i = 0; i < 1000; i++) cout << 1000 << ' ';
}