알고리즘261 [BOJ]1477번: 휴게소 세우기 문제: https://www.acmicpc.net/problem/1477 nnnyeong님 풀이를 참고하여 해결하였습니다. 이분 탐색을 활용한 결정 문제입니다. 결정 조건은 "휴게소 M개 사이의 거리를 distance 로 하였을 때 몇 개의 휴게소를 새로 세울 수 있느냐" 입니다. 그리고 이 distance 값을 이분탐색으로 찾으면서 M개 이하를 세울 수 있는 distance의 최솟값을 구하면 됩니다. M개 이하라고 한 이유는, M개 미만의 휴게소를 세워서 distance 조건을 만족할 수 있다면 휴게소를 한 개 씩 더 추가해서 distance를 더 줄일 수 있고 이렇게 늘려가다보면 결국 딱 M개의 휴게소를 세울 때의 거리가 정답 후보가 됩니다. 그 정답 후보들의 최솟값을 구해주면 됩니다. 코드: htt.. 2022. 3. 6. [PRGRMS]92335번: k진수에서 소수 개수 구하기 문제: https://programmers.co.kr/learn/courses/30/lessons/92335 시뮬레이션 문제입니다. 제일 중요한 조건은 '단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.'라는 조건입니다. 위 조건으로 인해 아래 3단계를 거쳐서 정답을 구할 수 있습니다. 1. 주어진 숫자를 k진수 변환 2. 0을 기준으로 split 3. 남아있는 숫자들에 대해 소수 판별 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/k%EC%A7%84%EC%88%98%EC%97%90%EC%84%9C%20%EC%86%8C%EC%88%98%20%EA%B0%9C%EC%88%98%20%EA%B5%AC%ED%95%98%EA%B8%B0.java 2022. 3. 5. [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. 이전 1 ··· 9 10 11 12 13 14 15 ··· 66 다음
