DP : 병사 배치하기 [백준 18353, Kotlin]

2023. 1. 24. 20:51· 알고리즘
목차
  1. [문제]
  2. [풀이]
  3. [코드]
  4. [출처]

[문제]

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

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

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

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

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

 

입력

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

출력

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

 

[풀이]

최장 증가 부분 수열 LIS로 바꾸어 푸는 방법 사용

최장 증가 부분 수열 : 배열을 오름차순으로 만들면서 크기가 가장 크게 만든다.

오름차순 → 내림차순으로 바꾸어 주기 위해 reverse 시키고 시작

soldier의 전투력이 더 작은 원소들 중 dp 의 최대값을 가져온다.

 

[코드]

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val soldiers = br.readLine().split(" ").map{it.toInt()}.reversed()
    val dp = MutableList(n){1}

    for(i in 1 until n){
        for(j in 0 until i) {
            if(soldiers[j] < soldiers[i])
                dp[i] = max(dp[i],dp[j]+1)
        }
    }
    println(n-dp.max())
}

[출처]

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

 

18353번: 병사 배치하기

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

www.acmicpc.net

 

'알고리즘' 카테고리의 다른 글

Dijkstra : 파티 [백준 1238, Kotlin]  (0) 2023.01.28
DP : 타일 채우기 [백준 2133, Kotlin]  (0) 2023.01.24
DP : 동전 1 [백준 2293, Kotlin]  (0) 2023.01.23
DP : 퇴사 [백준 14501, Kotlin]  (0) 2023.01.23
DP : 정수 삼각형 [백준 1932, Kotlin]  (0) 2023.01.22
  1. [문제]
  2. [풀이]
  3. [코드]
  4. [출처]
'알고리즘' 카테고리의 다른 글
  • Dijkstra : 파티 [백준 1238, Kotlin]
  • DP : 타일 채우기 [백준 2133, Kotlin]
  • DP : 동전 1 [백준 2293, Kotlin]
  • DP : 퇴사 [백준 14501, Kotlin]
베르_최성훈
베르_최성훈
베르의 안드로이드베르_최성훈 님의 블로그입니다.
베르_최성훈
베르의 안드로이드
베르_최성훈
전체
오늘
어제
  • 분류 전체보기 (57)
    • 우아한테크코스 (15)
    • Android (19)
    • kotlin (2)
    • 회고 (5)
    • Bug Fix (2)
    • 알고리즘 (6)
    • 기타 (1)
    • Jetpack Compose (6)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Test
  • 안드로이드
  • ViewModel
  • 프래그먼트
  • FRAGMENT
  • 페스타고
  • 우아한테크코스
  • coroutine
  • PRESENTER
  • flow
  • SharedFlow
  • MVVM
  • Kotlin
  • Lifecycle
  • 회고
  • MVP
  • 우테코
  • 생명주기
  • Android
  • 코틀린

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
베르_최성훈
DP : 병사 배치하기 [백준 18353, Kotlin]
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.