Algorithm/BOJ172 [BOJ]1477번: 휴게소 세우기 문제: https://www.acmicpc.net/problem/1477 nnnyeong님 풀이를 참고하여 해결하였습니다. 이분 탐색을 활용한 결정 문제입니다. 결정 조건은 "휴게소 M개 사이의 거리를 distance 로 하였을 때 몇 개의 휴게소를 새로 세울 수 있느냐" 입니다. 그리고 이 distance 값을 이분탐색으로 찾으면서 M개 이하를 세울 수 있는 distance의 최솟값을 구하면 됩니다. M개 이하라고 한 이유는, M개 미만의 휴게소를 세워서 distance 조건을 만족할 수 있다면 휴게소를 한 개 씩 더 추가해서 distance를 더 줄일 수 있고 이렇게 늘려가다보면 결국 딱 M개의 휴게소를 세울 때의 거리가 정답 후보가 됩니다. 그 정답 후보들의 최솟값을 구해주면 됩니다. 코드: htt.. 2022. 3. 6. [BOJ]6236번: 용돈 관리 문제: https://www.acmicpc.net/problem/6236 이분 탐색을 사용한 결정 문제입니다. Q. 한 번에 K원씩 인출해서 사용할 때 M번 이하로 인출이 가능한가? 위 조건을 만족하는 K의 최댓값을 구하면 됩니다. 중요한 건 하한과 상한값인데요. 하한은 max(N일 동안 생기는 지출)이 됩니다. 왜냐면 max(N일 동안 생기는 지출)보다 작으면 그 날에는 한 번의 인출로는 지출 금액을 감당할 수 없습니다. 그 다음은 결정 조건으로 'M번 이하'라고 했는데요. 원하면 언제든지 M번 횟수를 맞출 수 있으므로 M번 미만으로 인출해서 생활이 가능하다면 M번을 맞추는 건 무조건 가능합니다. 임의로 아무때나 추가 인출을 해서 사용하면 M번 미만 횟수가 M번이 됩니다. 위 두 가지를 고려해서 구현하.. 2022. 3. 3. [BOJ]2110번: 공유기 설치 문제: https://www.acmicpc.net/problem/2110 codueng님 풀이를 참고하여 해결하였습니다.(https://codeung.tistory.com/190) 이분 탐색을 활용한 결정 문제로 바꿉니다. Q. 첫 번째 집부터 공유기를 설치하여 mid 이상 거리인 집에만 설치해서 C개 이상을 설치할 수 있는 가? 위 조건을 만족하는 mid의 최댓값을 구하면 됩니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2110.java 2022. 3. 3. [BOJ]16724번: 피리 부는 사나이 문제: https://www.acmicpc.net/problem/16724 has2님의 풀이를 참고하여 해결하였습니다. (https://leesh111112.tistory.com/m/335) 주어진 그래프에서 싸이클의 갯수를 찾는 문제였습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ16724.java 2022. 3. 3. 이전 1 ··· 6 7 8 9 10 11 12 ··· 43 다음
