전체 글
2110번-공유기설치
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근방법 일반적인 이분탐색 문제와 유사하지만 기준으로 정한 거리(mid)값의 변화를 측정하기 위한 이전 인덱스를 변경하는 35번째 줄에서 약간의 구현력이 필요했던 문제였습니다. 그 외에는 일반적인 이분탐색 문제였습니다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..
1654번-랜선자르기
문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 접근방법 분할하였을 때 랜선의 개수가 n개 이상으로 만들어야 하는 경우에 랜선의 길이를 최대로 결정해야 하는 문제였습니다. 그렇기 때문에 이 문제에서는 탐색을 해야 하는데 n의 개수가 10000개 이므로 최악의 경우 100,000,000번의 연산이 발생하게 되므로 시간초과가 발생하여 O(logn)으로 시간복잡도를 낮춰야 하는 문제였습니다. 그러므로 이분탐색을 활용..
6236번-용돈관리
문제 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 접근방법 https://hyeophyeop.tistory.com/6 백준의 기타레슨과 매우 유사한 문제입니다. mid값을 어떻게 잡는가가 핵심이었던 문제였는데 저는 "현우가 당일날 사용할 수 있는 금액"으로 기준을 삼고 left값과 right값을 결정하였습니다. left값은 현우가 당일 사용하는 금액이 기준치보다 작으면 안됩니다. 왜냐하면 인출금액 K를 최소화하기로 했기 때문입니다. 그래서 lef..