K의 순서가 섞이면 안된다...;;;
최댓값을 최소화하는 형태 => 최적화문제
Wear level 의 최댓값이 어떤 정수 c가 되도록 k개의 덩어리를 선택할 수 있는가 (T/F 문제로 바뀜)
이분탐색으로!
어느 수를 기준으로 작은쪽은 불가능, 큰쪽은 가능으로 바뀌게된다. 이 수가 답!
그래서 가운데를 보자. 가운데가 가능하다면, 기준으로 왼쪽의 가운데 확인. 불가능하다면 오른쪽으로 이분탐색 지속.
C를 늘려가면서 블록들을 확인.
가장 앞의 블록을 가능한 가장 작은 인덱스부터 채워나가면서 가능한지 여부 확인.
이 C를 이분탐색으로 검색해가면서 확인한다.
그냥 완전탐색은 N! * N;;;
거기다가 N이 작아도 숫자도 계산해야하기때문에 거의 불가;;
정답 배치를 선택하고, 그 계산도중 나머지계산을 해가면서 해야한다.
정답 배치는, 그 중 i번째와 i + 1번째를 바꾼 배치보다 속력이 작거나 같을 수 밖에 없다.
특정한 구간부터 그 후의 배치가 같다면, 그 구간까지의 결과값에 따라 총 결과가 정해진다.
즉 (ai-1)/bi 값으로 내림차순 정리한 배치가 정답배치다.
=> 계산시 현재 속도 v는 지워져서 의미가읎다.
숫자의 갱신과 주어지는 구간 [a:b]에 대해서 원하는 연산을 log N의 시간복잡도로 해결해줄 수 있는 자료구조.
- 합이랑 최댓값, 최솟값, 곱셈 만 가능.
그냥 배열을 쓰면 교체, 연산 중 하나만 빠르고 다른건 느렸는데 얘는 평균적으로 log N
Divide & Conquer 도 가능하나, 어렵다
Indexed tree로 풀자!
풀이 :
- prefix tree
- use to find string
끝나는 위치를 색칠해줘야(숫자를적을수도) 알기쉽다. 슬라이드는 틀렸다
인접노드들끼리 인접한 주소값을 가지지 않을 경우가 훨씬많다.(추가된 시점이 완전다를테니까)
따라서 트라이는 cache unfriendly 하다. (지멋대로 메모리기ㅏ 건너뛰어진다. 캐시충돌이 많이 일어난다. 느리다.)
겁나느리다 따라서 포인터로 짜면 시간초과가 뜬다. 따라서 자식의 번호를 들고있는걸 추천. 포인터로 자식을 들고있는건 코딩엔 좋지만 시간엔 좋지않다.
동적계획법 .
우선 Cache를 만들어야한다.
Cache[N][L][R] N 개의 막대를 배치했을때 왼쪽에 L개가 보이고 오른쪽에 R개가 보이는 총 경우의수
모든 겨웅의수는 가장 짧은 마대가 가장왼쪽(1가지) , 가장 오른쪽(1가지), 가운데(N- 2가지)있는 3가지 경우로 나눌수 있다.
또 왼쪽에 가장작은게 있는 상황에서 (6, 3, 2) == (5, 2, 2)와 똑같다
마찬가지로 오른쪽에 가장 작은게 있는 상황에선 (6, 3, 2) == (5, 3, 1)
가운데 가장 작은게 있는 상황에선 (6, 3, 2) == (N - 2) * (5, 3, 2)
주어진 집합을 조건으로 쪼개는 걸 : 파티션
짜면 O(N ^ 3)
이걸 잘하면 O(N ^ 2)으로 할수있음...
그냥 접근시 O(N ^ 5)의 풀이가나옴.
모든 칸에 대하여,(N^2) 칸수를 정하고(N) 확인하고(N^2) = N^5