백준18353번 병사 배치하기 2021.06.16 병사배치하기 Solution LIS (Longest Increasing Sequence) 를 내림차순으로 변형하여 풀이하였습니다. 0 ~ N-1 을 돌며 DP[N]을 구합니다. (n) DP[N] = DP[N-i] + 1 (i = 0 ~ n-1) N-i번보다 N번이 작으면 N-i번 오른쪽에 N번이 위치할 수 있고, 이렇게 했을 때 N-i번의 최대 길이에 +1 한 것이 N번의 최대길이 후보가 됩니다. 0 ~ n-1 을 돌며 왼쪽 부분수열 중 n번이 오른쪽에 놓일 수 있는 후보를 고릅니다. +1 한 값과 비교해 DP[n]을 업데이트합니다. DP[N] 중 최댓값을 N에서 뺀 값이 정답입니다. Source # 2021.06.16 병사배치하기 # Solution :..

2020.02.18 algospot / LIS 풀이 수열이 맨 왼쪽부터 하나씩 들어온다고 했을 때,다음 숫자가 들어왔을 때 그보다 작은 숫자들 중 최대인 녀석을 찾고 거기에 +1 한 값과 DP에 써져있는 값을 비교해서 큰 녀석을 DP에 update 한다. 이와 같은 풀이를 진행하면 C = 50, N = 500, 모든 수가 1~ 100000을 다 지나간다고 했을 때 대략 50 * 500 * 100000 정도의 시간복잡도가 될 거고 이는 25억이 되어 시간초과가 발생할 거라 생각했다. update하면서 가장 큰 최댓값을 기억해두고 마지막에 이를 출력한다. 해당 숫자를 맨 오른쪽 끝으로 하는 수열의 길이를 DP에 적어둔다. 1번의 알고리즘에서 들어온 숫자를 DP에 update하는 알고리즘은 동일하지만 들어온 ..