개발왕 찌 (۶•̀ᴗ•́)۶

날짜 분류 번호 알고리즘 분류 링크 21-01-19 BOJ 20366 이분탐색 www.acmicpc.net/problem/20366 문제 요약 N개의 눈덩이 중 4개를 골라 눈두덩이 2개로 만들어진 눈사람 2쌍을 만든다. 이중 두 눈사람의 키 차이가 최소가 되는 값 구하기 눈덩이의 키 = 지름 풀이 눈덩이의 키 순서로 정렬 정렬된 상태에서 a, b, c, d 순차적으로 골랐다고 가정했을 때 a+d와 b+c의 차이가 abcd로 만들수 있는 눈사람의 키 차이임 a, b, d를 3중 for문으로 돌리고(ㅌㅋㅋㅋ ㅠㅠ ) 나머지 c를 b+1과 d-1 사이에서 c의 값 찾기... lower bound로 c의 값 구함 c-1의 값도 고려함 (c-1와 a, b, d가 다를 경우에만) 비고 N이 600인데 시간 제한이..

날짜 분류 번호 알고리즘 분류 링크 21-01-20 BOJ 2585 이분탐색&bfs www.acmicpc.net/problem/2585 문제 요약 (0, 0)에서 (10000, 10000)까지 이동할 수 있는 최저의 연료통 용량 구하기 단, 중간에 주유를 할 수 있는 횟수는 K번 이하여야 함 참고사항 연료의 단위는 1L이며 1L당 10km 비행 가능 두 지점의 거리는 평면상의 거리임 풀이 (0, 0)에서 (10000, 10000)까지 필요한 연료량을 r(최대값)으로 두고 이분탐색 진행 mid로 목적지까지 도착할 수 있는지 없는지를 확인 bfs 사용 que에서 좌표를 하나 꺼내고 주어진 연료량으로 목적지까지 갈 수 있으면 true 반환 목적지까지 갈 수 없는데 연료횟수가 K번이면 다음 좌표로 넘어감 목적지..

문제 요약 x 축에 사대가 있고 (a,b)에 동물이 존재함 사대로부터 거리가 L 이하인 동물만 잡을 수 있다고 가정했을 때 잡을 수 있는 동물의 수 찾기 사대의 위치 x와 동물의 위치 (a, b) 간의 거리는 |x-a| + b 풀이 동물들의 위치를 기준으로 반복문으로 돌림 해당 동물을 잡을 수 있는 사대는 y좌표 - (L-x좌표)부터 y좌표 + (L-x좌표) 사대의 위치를 정렬하여 min 값보다 크거나 같은 사대의 idx를 구함 (lowerbound) 해당 idx의 사대 위치가 min 이상 max 이하일 경우 정답에서 1 증가 또 또 또 블로그 글을 보고 힌트를 얻은,,, ㅠㅠ 어차피 min의 값보다 같거나 큰 gun의 위치를 찾는 건데 if (gun[idx] = min && gun[idx] 0 ? mi..