목록가장 긴 증가하는 부분 수열: o(n log n) (1)

영원히 남는 기록, 재밌게 쓰자

백준 [18353] 병사 배치하기 (자바)

문제풀이앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사의 전투력보다 높게 병사를 배치해야 한다.내림 차순으로 가질 수 있는 가장 긴 수열을 찾는 문제 (LDS) DP를 사용해서 풀이(N 최대가 2000)0 ~ N - 1 번째 병사까지 탐색dp[i] = 1로 초기화i번째 병사보다 앞에 있는 병사들을 탐색 (0 seq[j] > seq[i] 이고 dp[i] max = Math.max(max, dp[i])로 가장 긴 부분 수열 길이를 저장N - max를 출력정답코드package com.baekjoon.p18353;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOExc..
Algorithm/백준 2024. 6. 14. 12:10
이전 Prev 1 Next 다음