[백준 15311] 약 팔기 [Java]

문제

http://boj.ma/15311

15311번: 약 팔기

 

---

풀이

문제 요약

길이가 최대 2,000인 수열의 연속된 부분 수열의 합으로 최대 1부터 N까지의 모든 수를 나타내야 한다.

아이디어

구성되는 수열이 꼭 최소일 필요가 없다. 또한 연속된 부분 수열로 1부터 100만 까지 표현해야 한다.

동일한 수로 구성되지 않는다면 수의 위치에 따라 표현할 수 있는 수가 제한받는다.

K는 최대 2000이며, 100만은 1,000*1,000으로 표현할 수 있다. 1000 단위보다 작은 수는 999개의 1로 표현할 수 있다.

따라서 999개의 1과, 1,000개의 1,000으로 모든 수를 표현할 수 있다.

        // Solve
        int[] res = new int[1999];
        Arrays.setAll(res, i -> i < 999 ? 1 : 1000);

풀이 시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/hard/15311.java

problem-solving/baekjoon-online-judge/hard/15311.java at main · rogi-rogi/problem-solving