BOJ 15311 - 약 팔기

문제

BOJ 15311 - 약 팔기

길이가 N인 수열을 출력해야 한다. 이 수열에서 임의의 연속 부분 수열의 평균은 1 이상 1000 이하인 정수여야 한다. N이 최대가 되도록 수열을 구성하고, N과 수열을 출력하라.

입력

입력이 없다.

출력

첫째 줄에 N을 출력하고, 둘째 줄에 N개의 수를 공백으로 구분하여 출력한다. 연속 부분 수열의 모든 평균이 1 이상 1000 이하인 정수여야 한다.

예제

출력:

2000
1 1 ... 1000 1000 ...

풀이

핵심 아이디어: 평균이 항상 정수가 되려면 모든 원소가 동일하거나, 특별한 구조를 가져야 한다. 임의의 연속 부분 수열의 평균이 정수가 되는 조건을 만족하면서 N을 최대화해야 한다.

핵심 관찰:

• 1과 1000만을 원소로 사용하면, 연속 부분 수열의 합이 정수가 되는 조건을 분석할 수 있다.
• 1이 K개, 1000이 K개인 수열(총 2K개)에서 1만으로 구성된 부분 수열 평균은 1, 1000만으로 구성된 부분 수열 평균은 1000이다.
• 그러나 1과 1000이 섞인 부분 수열의 평균이 정수가 되려면 특별한 배치가 필요하다.
• 검증된 해: 1을 1000개, 1000을 1000개 나열하면 N = 2000이 된다. 어떤 연속 부분 수열도 1로만 구성되거나 1000으로만 구성되거나, 1이 앞부분 1000의 일부와 1000이 뒷부분 1000의 일부로 구성된다. 1만 선택하면 평균 1, 1000만 선택하면 평균 1000이고, 섞인 경우에도 평균이 정수가 되는 것이 이 배치의 핵심이다.
• 이 구성이 최대 N = 2000임이 수학적으로 증명된다.

코드

package day349;
 
public class Day327BOJ15311약팔기 {
    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        sb.append("2000\n");
        for (int i = 0; i < 1000; i++) {
            sb.append("1 ");
        }
        for (int i = 0; i < 1000; i++) {
            sb.append("1000 ");
        }
        System.out.println(sb);
    }
}

복잡도

• 시간: O(N) — 수열 생성 (N = 2000 고정)
• 공간: O(N) — 출력 버퍼