문제 문제 바로가기> BOJ 8983번: 사냥꾼 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 풀이 중요한 포인트는 "사대를 기준으로 동물을 보는 것"이 아니라, "동물을 기준으로 사대를 보는 것"이다. 사대를 정렬해두고, 해당 동물을 잡을 수 있는 사대가 있는지 이분탐색을 이용하여 확인하면, MlogM(사대 정렬) + NlogN(나를 잡을 수 있는 사대 찾기) → O(MlogM) 만에 문제를 해결할 수 있다. #include #include #def..

문제 개구리가 연못 위에서 놀고 있다. 개구리는 N개의 연 잎 들을 이용해서 이리저리 뛰어 놀고 있다. 개구리가 뛰는 장면을 보던 철수는 개구리가 도약을 하는 경우가 얼마나 있는지 궁금해졌다. 여기서 도약은 아래 조건을 만족하는 경우를 말한다. 1. 개구리가 뛴 거리가 이전에 뛴 거리 이상 뛰지만 그 2배보다 멀리 뛰지는 않는다. 2. 개구리는 오른쪽으로만 뛴다. 3. 개구리는 두 번만 뛴다. 4. 위 세 가지 조건을 만족한다면 어느 곳에서든 시작할 수 있다. 허나, 연 잎 들이 너무 많기 때문에 가능한 횟수가 매우 많아질 것 같다고 생각한 철수는, 개구리가 오른쪽으로 도약하는 경우가 얼마나 되는지 구해달라고 했다. 철수를 위해 프로그램을 짜주자. 첫 번째 줄에는 연 잎의 수 N(3 ≤ N ≤ 1,000..

문제 문제 바로가기> BOJ 16434번: 드래곤 앤 던전 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 풀이 이분 탐색을 이용해, "용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를"를 구해주었다. HMaxHP의 범위는 int 범위를 넘어갈 수 있기 때문에, long long 으로 설정해주어야 하며, 용사와 몬스터의 전투 과정 또한 반복문을 통해 일일이 해보는 것이 아닌, 수식 계산을 통해 해주어야 한다! ( ex 용사의..