[자바] 백준 10471 - 공간을 만들어 봅시다 (java)

목차

문제 : boj10471

 

 

필요 알고리즘

• 브루트포스
  
  • 모든 경우를 확인해서 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  이 문제는 0, W, 그리고 입력받은 P개의 파티션(0 < P < W) 총 P+2개에 대해 모든 쌍을 확인해 차이를 확인하면 되는 문제이다. 모든 경우를 보면 되므로 브루트포스(완전탐색) 이다.

 

  그렇게 해도 O(P^2) 이므로 시간이 충분하다!

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Math.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());

        boolean[] room = new boolean[w+1];
        List<Integer> list = new ArrayList<>(p+2);
        list.add(0);
        list.add(w);
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < p; i++) {
            int cur = Integer.parseInt(st.nextToken());
            for (int partition : list) {
                room[abs(cur - partition)] = true;
            }
            list.add(cur);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= w; i++) {
            if (room[i])
                sb.append(i).append(' ');
        }
        sb.append(w);
        System.out.println(sb);
    }
}