[백준] 15311번 - 약팔기 (Java)

문제

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

15311번: 약 팔기

 

입력

 

출력

---

알고리즘

수학, 애드 훅, 해 구성하기

 

문제를 보자마자 모든 값을 커버해야 되니깐 이진수를 쓰면 되지 않나..? 라고 생각할 수 있다. 하지만 이 문제에는 함정이 있다. 반드시 연속된 자리에 있어야되기 때문이다. 따라서 이 방법으로 풀 수 없다.

 

이 문제는 입력이며 예제며 되게 거창하게 주어져있는데 싹다 함정이다. 다 필요없다. n = 1000000이 될때까지 다 커버할 수 있게 약봉지를 만들어두면 n값에 관계없이 답은 동일하게 나온다.

 

그냥 1개씩 든 약봉지를 1000개 쫘르륵 두고, 1000개 든 약봉지를 1000개 쫘르륵 둔다면 1알을 요구하든, 50만 5천알을 요구하든, 100만알을 요구하든 어떤 숫자가 오던간에 연속으로 약봉지를 집었을 때 그 숫자를 만들 수 있다.

 

따라서, 1을 1000개, 1000을 1000개 출력해주면 답이다. 굉장히 신박한 문제고, 이를 생각하지 못한다면 굉장히 삽질할 수 있는 악질 문제이다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        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);
    }
}