박카스러버

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 저는 2중 for문, 이분탐색, 투포인트를 통해서 해결하였습니다. 2중 for문을 통해 두 수의 합이 목표 합과 같아지는 개수를 확인하였고, 이분탐색과 투포인트는 정렬후 진행하였습니다. 이분탐색은 목표 수에서 해당 수를 뺸 값이 존재하는지를 확인하여 문제를 풀었습니다. 이때 해당 수보다 뒤에 있는 것만 확인하였습니다. 투포인트는 맨앞과 맨 뒤..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 저는 크루스칼을 통해 문제를 해결하였습니다. (정점의 개수)^2 보다 간선의 개수 작기 때문에 크루스칼이 더 유리하다 판단하여 크루스칼을 통해 문제를 해결하였습니다. 크루스칼의 경우 Elog(E)의 시간복잡도를 갖아 더 유리하여 이를 활용하여 문제를 풀었습니다. package BOJ.mst; import java.io.BufferedReader; im..

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 저는 투포인트를 통해 문제를 해결하였습니다. 투 포인트를 통해 그 사이에 특정 숫자들이 몇개 있는지를 확인하고 이 개수가 m를 파악합니다. 이때 m보다 크다면 startIndex를 줄여 사이 길이를 줄이면서 가장 긴 길이를 찾아 문제를 해결하였습ㄴ디ㅏ. package BOJ.twopoint; import java.io.BufferedReader; import java.io.InputStrea..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 저는 LIS를 통해 문제를 풀었습니다. A를 기준을 봤을 때 A가 증가함에 따라 B가 증가한다면, 전기줄들은 만나지 않을 것 입니다. 그래서 최장 증가수열을 구하고 이 값을 n에서 뺸 값을 통해 문제를 풀었습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public..

https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 저는 투포인트를 통해 문제를 풀었습니다. 투포인트로 그 사이 간격이 x인 경우 그 사이의 합을 구하고, 이 값들의 최대 값을 추적하여 문제를 해결하였습니다. package BOJ.twopoint; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public cla..

https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 저는 이분탐색을 통해 문제를 풀었습니다. 해당 질투심으로 나눠줄 수 있는지를 파악하여, 나눠줄 수 있다면, end값을 그렇지 않다면 start값을 조정하여 문제를 풀었습니다. package BOJ.binarysearch; import javax.sound.sampled.Port; import java.io.BufferedReader; import java.io.InputStreamReader; im..

https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 저는 DP를 이용해 문제를 풀었습니다. DP를 이용해 이전에 계산한 것을 다시 계산하지 않도록 하여 시간안에 동작하도록 구현하였습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ_21317_2 { public static void main(String[] args) throws Except..

https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 저는 BFS를 통해 문제를 풀었습니다. BFS를 통해 두개 동전이 갈 수 있는 경우의 수를 모두 찾아 문제를 풀었습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.St..

https://www.acmicpc.net/problem/19621 19621번: 회의실 배정 2 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net 저는 DP를 이용해 문제를 풀었습니다. DP를 통해 이전에 계산한 것을 다시 계산하지 않도록 하여 문제를 풀었습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BOJ_19621_2 { private static class Meeti..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 저는 DP를 이용하여 문제를 풀었습니다. DP를 이용해 이전에 계산한 것을 다시 계산하지 않도록하여 제한시간안에 풀었습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_1890 { public s..