[백준OJ] 1365번 꼬인 전깃줄

[백준OJ] 1365번 꼬인 전깃줄

728x90

반응형

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

풀이

말을 살짝 바꿔서 잘라야되는 전깃줄을 구하는것이아닌, 자르지 않아도되는 전깃줄의 최대값을 구해준다고 생각을 하면 쉽게된다.

그럼 여기서 자르지않아도 되는 전깃줄의 최대값은 어떻게 구해줄까? 방법은 바로 증가하는 수열의 최대길이를 구해주면된다.

이를 위해 Lower_bound함수를 구현해준 뒤, 자르지않아도 되는 전깃줄의 최대값을 구해주어 N에서 빼주면 답이 나온다.

시간복잡도

Lower_bound의 시간은 O(logN)이 되는데, 이를 N번 반복하기때문에 O(NlogN)이 된다.

코드

import java.util.ArrayList; import java.util.Scanner; public class Main { static ArrayList v=new ArrayList<>(); static int n; static int lower_bound(int num){ int l=0; int r=v.size(); while(l>1; if(v.get(middle)>=num){ r=middle; } else{ l=middle+1; } } return l; } public static void main(String[] args){ Scanner scanner=new Scanner(System.in); n=scanner.nextInt(); for(int i=0;i=v.size()){ v.add(line); } else{ v.set(ind,line); } } System.out.println(n-v.size()); scanner.close(); } }

반응형

from http://khu98.tistory.com/301 by ccl(A) rewrite - 2021-11-07 23:01:33