본문 바로가기

전체 글361

[PRGRMS]67258번: 보석 쇼핑 문제: https://programmers.co.kr/learn/courses/30/lessons/67258 투 포인터로 해결할 수 있는 문제입니다. 구간의 시작점(st)과 구간의 끝점(en)에 있는 모든 보석을 구매합니다. st값이 1씩 증가할 때 마다 이전 st값이 가리키는 인덱스에 있던 보석을 지웁니다. en값이 1씩 증가할 때 마다 새로운 en값이 가리키는 인덱스에 있는 보석을 더합니다. 단, 예외 케이스를 신경써야하는 부분이 있습니다. 1. 구간의 시작점에 있는 보석을 2개이상 가지고 있는 경우, 구간의 크기를 하나 줄여도(구간의 시작점 + 1) 보석의 구매상태는 변하지 않으므로 구간 크기를 줄일 수 있습니다. 2. 모든 보석을 구매한 경우 구간의 시작점 + 1을 하여 다음 정답 구간이 존재하는.. 2022. 3. 4.
[PRGRMS]81302번: 거리두기 확인하기 문제: https://programmers.co.kr/learn/courses/30/lessons/81302 시뮬레이션 문제입니다. N제한이 작으므로 완전 탐색을 통해 해결합니다. BFS를 사용하여 지원자들간의 거리를 구하였고 맨헤튼 거리가 2이하인 경우만 표시해주면 됩니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0%20%ED%99%95%EC%9D%B8%ED%95%98%EA%B8%B0.java 2022. 3. 3.
[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.

티스토리툴바