[이코테] 병사 배치하기(Python) / 백준 / 삼성SW 역량테스트

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

18353번: 병사 배치하기

 

 

 

 

 

문제

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

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

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

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

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

입력

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

 

출력

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

 

예제 입력 및 출력

## 입력
7
15 11 4 8 5 2 4

## 출력
2

 

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

 

 

문제풀이

그냥 크기 비교해서  뒷 값이 클 때마다 증가해서 풀면 되지 않을까라고 생각했고 예시의 입력을 실행했을 때도 답도 나왔다.

하지만 반례가 있었다.

내 코드의 문제점은 단순하게 현재값과 그다음 값의 크기 비교만으로 카운트를 하는 것이다.

문제에서는 병사들의 전투력을 내림차순으로 정렬하며 열외 하되, 남아 있는 병사의 수를 최대화 시키는 것이 목적이다.

문제의 목적을 제대로 파악하지 않았다.

## 이코테[백준] - 18353
import sys
input = sys.stdin.readline

n = int(input())
army = list(map(int, input().split()))

cnt = 0
for i in range(0, n-1):
    #print(army[i])
    if army[i] < army[i+1]:
        cnt += 1
print(cnt)

 

 

책의 풀이 참고

문제의 기본 아이디어 : 가장 긴 증가하는 부분 수열(LIS)

→ 변형 : 가장 긴 감소하는 부분 수열

 

j는 0에서 i-1까지의 값들을 i와 비교한다.

→ i : 비교하려는 마지막 값, j :  0에서 i-1까지의 값

이라고 생각하면 이해하기 쉽다.

마지막 값과의 비교하며 앞 값(j)이 뒷 값(i) 보다 크다면, 문제의 조건과 맞기 때문에(내림차순) count [i]와 count [j]+1 값을 비교하여 더 큰 값을 count에 저장한다.

만약, 앞 값(j)이 뒷 값(i) 보다 작을 경우, 즉, 감소하는 형태가 아닐 경우에는 count[i]의 값에 변화가 없다.

이 과정을 거친 후, 최종적으로 우리가 원하는 값은 최대로 병사가 남아있을 수 있도록 하는 열외되는 수이다.

최대로 병사가 남는 것 == 가장 긴 감소 수열의 길이 == count의 최댓값

그러므로 전체 병사의 수 (n)에서 가장 긴 감소 수열의 길이(max(count))를 빼면 문제에서 원하는 열외 되는 수를 구할 수 있다.

 

## 이코테[백준] - 18353
import sys
input = sys.stdin.readline

n = int(input())
army = list(map(int, input().split()))

count = [1]*n  ## 조건만족하는 값 저장

for i in range(1, n):
    for j in range(0, i):
        if army[j] > army[i]:
            count[i] = max(count[i], count[j]+1)
            
print(n-max(count))

 

 

느낀 점

책의 풀이뿐만 아니라 다른 사람들의 풀이도 찾아봤는데, 다들 LIS 알고리즘을 다 알고 있었다.

그래서 또 나만 모른 것 같아서 조금 머쓱했다...^^;

그래도 하나 알아갑니다~