18353번 - 병사 배치하기

가장 긴 오름차순 수열 문제에서 한번 꼰 문제입니다.
분석을 할 수 있으면 어렵지 않게 풀 수 있습니다.

분석

위 수열에서는 2,5,3,2,15 라는 체크해둔 수열을 제외하면 병사의 수가 최대가 되도록 할 수 있습니다.
그런데 체크해 둔 수열을 제외하면 뭔가 규칙성이 보이실 겁니다. 맞습니다. 바로 최장 증가 수열입니다.

한마디로 lst를 reverse 시킨 다음 전체 수열의 길이 - 최장 증가 수열의 길이 를 구한 값이 결국 열외해야 하는 병사의 수가 된다고 보시면 될 것 같습니다.

코딩

N = int(input())
lst = list(map(int,input().split()))
lst = list(reversed(lst))
dp = [1]*len(lst)

lst를 선언해주고 뒤집겠습니다. 갯수를 세야하므로 dp값은 전부 1로 초기화하겠습니다.

for i in range(len(lst)):
    maximum = 0
    for j in range(i):

최장 부분 수열을 구해주기 위해서 maximum을 하나 선언해줍니다.

        if lst[i] > lst[j]:
            if maximum < dp[j] + 1:
            	maximum = dp[j] + 1

현재 조사중인 인덱스가 이전에 조사중인 인덱스보다 크다면
이전 dp값들 중에서 가장 큰 값 ( 인덱스 전까지의 가장 긴 최장 증가 수열 길이 ) + 1을 maximum에 대입해줍시다.

dp값을 가시화하면 이러한 형태로 나오게 됩니다.

                dp[i] = maximum

그리고 해당 maximum에서 이미 수열 길이 + 1 처리를 해주었으니 dp값에 바로 넣어줍시다.

print(len(lst)-max(dp))  

마지막으로 전에 언급한대로 전체 수열의 길이 - 최장 증가 수열의 길이 를 출력하면 답이 나옵니다.

소마 서류지원에 합격했습니다.

프로젝트 경험이 적고 무언가를 만들어보고 싶은 제 입장에서 소마 연수생이 된다면 더없이 좋은 기회일 것 같습니다.

제 실력이 아직 미흡하고, 아마 합격되지 않을 것이라는걸 잘 알지만 여태 공부한 게 헛되지 않도록 열심히 풀어보겠습니다.