박카스러버

https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 저는 DP를 이용하여 문제를 해결하였습니다. 저는 DP를 dp[depth][소형기관차를 사용한 횟수]로 지정하여 문제를 풀었습니다. 함수는 기관차를 사용하지 않는다면 다음 뎁스로 사용한다면 객차를 끌 수 있는 수 만큼의 다음 뎁스로 넘어가면서 답을 구하였습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStream..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 저는 DP를 이용하여 문제를 해결하였습니다. DP를 이용해 각 경우의 수의 최소값과 최대값을 확인하였습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; import java.util.function.Func..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 저는 우선순위 큐를 통해 문제를 해결하였습니다. 저는 역순으로 생각하였습니다. 먼저 가장 늦은 시간부터 할 수 있는 일을 우선순위 큐에 넣었습니다. 그리고 해당 시간에 가장 큰 값을 더해주고 위의 방법을 반복하여 문제를 해결하였습니다. package BOJ.greedy; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; imp..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 저는 각각의 전기용품마다 큐를 만들어 해결하였습니다. 해당 큐를 통해 다음 인덱스가 어디인지 확인하고 가장 먼 인덱스를 갖고 있는 멀티탭에 있는 전기용품을 빼고 현재 것으로 교체하여 문제를 해결하였습니다. package BOJ.greedy; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Linked..

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 저는 투 포인트를 이용해 문제를 해결하였습니다. 일단 엔드 포인트를 옮기면서 현재 값의 cnt를 늘립니다. 이 값이 k보다 크다면 이 값이 k보다 같거나 작아질 때 까지 시작 포인트를 늘리면서 해당하는 값의 cnt를 줄여나갑니다. package BOJ.twopoint; import java.io.BufferedReader; import java.io.InputStreamReader; impo..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 저는 DP를 이용하여 문제를 해결하였습니다. DP를 이용하여 이전의 계산된 값을 저장하였고, 저는 문제를 재해석하였습니다. 마지막 계단을 무조건 밟아야하기 때문에 마지막 계단에서 맨 밑에 까지 내려오면서 점수가 가장 큰 값을 계산하여 문제를 해결하였습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; impor..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 저는 투 포인트를 이용해 문제를 해결하였습니다. 투 포인트를 통해 해당 포인터 사이의 합을 구하고 이 값을 s와 비교하여 작다면 끝 포인트를 늘리고 작거나 같다면 시작 포인트를 늘리면서 합이 s 이상인 길이를 추적하여 최소의 값을 찾았습니다. package BOJ.twopoint; import java.io.BufferedReader; import java.io.InputStream..

https://www.acmicpc.net/problem/14235 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 저는 우선순위 큐를 통해 문제를 해결하였습니다. 0인 경우 우선순위 큐에서 하나 뽑고 그렇지 않다면 우선순위 큐에 선물을 저장하였습니다. package BOJ.greedy; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; ..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 저는 우선순위 큐를 이용해 문제를 해결하였습니다. 우선순위 큐를 통해 작은 값 두개를 가져오고 이 값을 합하여 다시 우선순위 큐에 넣어주어 문제를 해결하였습니다. 총 카드의 합이기 때문에 작은 값 두개를 합해야한다고 생각했습니다. 만약 카드가 1개라면 그 카드를 바로 리턴하도록 하였습니다. package BOJ.greedy; import java.io.Buff..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 저는 우선순위 큐를 이용해 문제를 해결하였습니다. 각각의 일이 이전에 몇개의 작업이 필요한지를 세고 이 값이 0인 값만 먼저 우선순위 큐에 넣었습니다. 우선순위 큐에 빼면서 해당 작업이 필요했던 작업의 필요한 작업 개수를 줄이고 해당 값이 0 이라면 우선순위 큐에 넣어서 문제를 해결하였습니다. package BOJ.greedy; import java.io.Buffer..