🥈 [Baekjoon / Java] 18353. 병사 배치하기

문제 설명

💡 Info

• 난이도 : 실버 2
• 시간 제한 : 1초
• 메모리 제한 : 256MB
• 백준 링크: https://www.acmicpc.net/problem/18353
  풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Silver/18353. 병사 배치하기

내용

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

📥입력 조건

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000)
• 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다.
• 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

7
15 11 4 8 5 2 4

📤출력 조건

• 첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.

2

문제 이해

• 열외해야하는 병사의 수를 계산 -> 남아있는 병사의 수가 최대가 되게!
  • 전투력이 높은 병사가 앞쪽에 오게 내림차순 배치
  • 특정한 위치에 있는 병사를 열외시키는 방법을 이용, 그러면서도 병사의 수가 최대가 되도록 하기

알고리즘

실제 풀이 시간 : 12분

• 입력

  • N 입력받기
  • 병사 번호, 전투력 배열 입력받기

• 계산

  • d로 테이블 초기화하기
  • 내림차순 정렬하기
  • 바텀업으로 구현
    • Math.max로 최대 병사의 수 구현
    • 전체 - 열외 병사 수로 출력

• 출력

  • 전체에서 최대값 제거해서 결과 출력

import java.util.*;

public class Main {

    static int N;
    static int[] d;
    static int maxSol;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        Integer[] arr = new Integer[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr, Collections.reverseOrder());

        d = new int[N];
        Arrays.fill(d, 1);

        for(int i = 1; i<N; i++){
            for(int j = 0; j< i; j++) {
                if(arr[j] > arr[i]){
                    d[i] = Math.max(d[i], d[j]+1);
                }
            }
        }

        for(int i=0; i<N; i++){
            maxSol = Math.max(maxSol, d[i]);
        }
        System.out.println(N - maxSol);

    }
}

오답체크

• 정렬을 하고 나서 계산을 진행하니 문제 발생
  • 정렬 제거하고, 바로 Arrays.fill 진행하도록 해 해결

//before
Arrays.sort(arr, Collections.reverseOrder());

d = new int[N];
Arrays.fill(d, 1);

//after
d = new int[N];
Arrays.fill(d, 1);

최종 풀이

실제 풀이 시간 : 20분(첫 풀이 시간 포함)

• 입력

  • N 입력받기
  • 병사 번호, 전투력 배열 입력받기

• 계산

  • d로 테이블 초기화하기
  • 바텀업으로 구현
    • Math.max로 최대 병사의 수 구현
    • 전체 - 열외 병사 수로 출력

• 출력

  • 전체에서 최대값 제거해서 결과 출력

import java.util.*;

public class Main {

    static int N;
    static int[] d;
    static int maxSol;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        Integer[] arr = new Integer[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        d = new int[N];
        Arrays.fill(d, 1);

        for(int i = 1; i<N; i++){
            for(int j = 0; j< i; j++) {
                if(arr[j] > arr[i]){
                    d[i] = Math.max(d[i], d[j]+1);
                }
            }
        }

        for(int i=0; i<N; i++){
            maxSol = Math.max(maxSol, d[i]);
        }
        System.out.println(N - maxSol);

    }
}