박카스러버

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 저는 투포인트를 통해 문제를 풀었습니다. 투포인트를 통해 해당 포인트 사이의 합을 구하고 이 합이 목표값보다 작으면 앞쪽 포인트를 크다면 뒤쪽 포인트를 늘리면서 목표값이 크면서 인덱스 사이의 값이 작은 것을 찾아 문제를 풀었습니다. package BOJ.twopoint; import java.io.BufferedReader; import java.io.InputStreamReader..

https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 저는 DP를 이용하였습니다. 해당 depth부터 연속적으로 .이 몇개 있는지를 판단하여 AAAA 또는 BB를 넣을지를 판단하여 dfs를 통해 모든 경우를 찾았습니다. 이때 중복되는 경우는 다시 계산하지 안도록 하기위해 DP를 이용하였습니다. package BOJ.dp; import java.io.BufferedReader; import java.io.InputStreamReader; public class BOJ_1343 { public static void main(String[] args) thr..

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 저는 정렬을 통해 문제를 풀었습니다. 오름차순으로 정렬하여 현재 인덱스보다 뒤에 있는 값은 현재 값보다 크다는 것을 보장하였습니다. 즉, (전체 입력 길이 - 현대 인덱스) * 현재 무게가 현재 로프를 포함한 최대 무게입니다. 이를 바탕으로 인덱스를 점점 줄여나가면서 최대 값을 찾아 문제를 풀었습니다. import java.io.BufferedReader; import java.io.In..

https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 저는 정렬을 통해 문제를 풀었습니다. 내림차순으로 정렬하여 최대한 빼는 수를 적게 하여 풀었습니다. package BOJ.greedy; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collections; public class BOJ_..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 저는 자료구조에서 큐를 통해 풀었습니다. 큐를 통해 맨 앞에 것을 꺼내고, 또 맨 앞에 것을 꺼내어 맨 뒤에 넣는 것을 반복하여 최후의 한 장이 무엇인지 찾아 문제를 해결하였습니다. package BOJ.dataStructure; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; ..

https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 저는 크루스칼을 통해 문제를 풀었습니다. MST 방법 중 크루스칼을 통해 MST를 구하였습니다. n과 m의 범위가 같기 때무넹 크루스칼이 더 유리하다 판단하였습니다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Test { private static class Edge{ int ..

https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 저는 프림을 통해 문제를 해결하였습니다. 프림을 통해 모든 행성을 연결하면서 최소 비용을 구하여 문제를 해결하였습니다. package BOJ.mst; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util...

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 저는 BFS를 통해 문제를 해결하였습니다. 1에서 BFS를 시작하여 연결되어 있는 노드의 개수를 확인하여 문제를 풀었습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BOJ_2606 { public static void main(String..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 저는 for문과 이분 탐색을 통해 문제를 풀었습니다. for문으로는 0부터 최고값까지 해보면서 합이 M보다 큰지를 판단하여 크다면 결과값을 초기화하여 문제를 풀었습니다. 이때 시간복잡도는 n*최고값이기 때문에 1초 이내로 동작하기 힘듭니다. 이분탐색의 경우, 합이 M보다 큰지를 판단하여 크다면 start값을 작다면 end값을 변경하면서 가장 큰 값을 찾았습니..