kthng

boj 11060 : 점프점프 https://www.acmicpc.net/problem/11060 삼성 코드그라운드에서도 비슷한 문제를 본 기억이 있다. 해결방법은 간단하다. dist[i]를 i번째 돌까지의 최소 점프 횟수, a[i]는 i번째 위치의 점프력이라고 두면 1. dist[j] = min(dist[j],dist[i] + 1) { i+1

boj 2343 : 기타 레슨 https://www.acmicpc.net/problem/2343 얼핏 보면 간단하지만, 아이디어가 쉽게 떠오르지 않아 고생했던 문제이다.ㅜㅜ 1. f(a) : 블루레이 크기가 a일 때 M개 모두 녹화할 수 있는가? true or false2. f(a)가 true인 최소의 a값이 답이다. 이분탐색을 이용하면 시간안에 문제를 해결할 수 있다.f()의 시간복잡도는 n, 이분탐색의 시간복잡도는 logn이므로 총 시간복잡도는 nlogn이다.

boj 11501 : Stock(주식) https://www.acmicpc.net/problem/11501 언뜻 간단해보이지만 아이디어를 떠올리기가 쉽지만은 않은 문제이다. a[i]를 i번째 주식의 가격이라 할 때, i번째를 산다면 얼마에 팔 수 있는가?term_max를 팔게될 가격이라고 한다면, 1. term_max = max(a[k]) {k = i~n} 그렇다면 이득은 얼마인가? 2. i번째 얻는 이득 : term_max - a[i]; 위 알고리즘의 시간복잡도는 n이다.