목록2024/03/04 (2)
delpho
Think 1. 하 DP.... 정말 어렵다 문제에 주어진 조건을 성립하면서 DP로 푸려는 아이디어가 어려웠다. 2. https://st-lab.tistory.com/132 를 참고했다. 제출 코드 (Top-down) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class test { static int n; static int sequence[]; static Integer dp[]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); stat..
Think 1. LIS인 이 문제를 보고 고민해보았으나, 풀이 접근 방법이 떠오르지 않음 (이걸 dp로 어떻게 풀지..? 라는 생각) 2. https://st-lab.tistory.com/137 를 참고하여 풀이 방법을 공부함 3. 현재 수열 기준으로 이전 값들을 탐색하며 이전 값이 더 작다면 해당 인덱스의 dp 값 + 1과 현재 dp값을 비교하여 최대값을 저장해준다 4. 해당 풀이법은 시간복잡도가 N^2라고 하며, 이분탐색을 활용하면 NlogN까지 가능하다고 함 제출 코드 (Top-down) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public..