공부공간

https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 이문제의 정해는 이분탐색으로 찾는것이지만, 정답의 범위가 0-1000사이 이므로 휴게소 사이의 거리의 최솟값을 시작값으로, 최댓값을 종료값으로하고 FOR문으로 하나하나검사해도 풀린다. 시작과 끝 0 과 L 위치의 휴게소가 있다고 생각하고 각 휴게소 사이의 거리를 측정한다. => 최솟값과 최댓값사이의 값하나가 휴게소의 거리라 생각하고, 몫 -1 ( 나누어 떨어질때 ) Or..

https://www.acmicpc.net/problem/17081 17081번: RPG Extreme 요즘 택희는 RPG 게임을 하고 있다. 던전을 헤쳐나가며 몬스터를 물리치고, 아이템을 모으고, 레벨 업을 하여 보스 몬스터를 물리치는 전형적인 RPG 게임이다. 이 게임은 N×M 2차원 그리드 위에서 � www.acmicpc.net 풀지마세요.. 문제 조건대로 하나하나 코딩하면 됩니다.. ㅠ package algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.ArrayList; import j..

https://www.acmicpc.net/problem/1846 1846번: 장기 N개의 줄에 걸쳐, 게임판에서 각 줄의 몇 번째 칸에 차를 배치했는지를 나타내는 칸의 번호를 순서대로 출력한다. 조건을 만족시키는 배치가 둘 이상이면 아무 것이나 출력한다. 배치가 불가능�� www.acmicpc.net 잘 보면 규칙이 나온다.. package algorithm; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class 장기 { public static void main(String[] args) throws..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 블록을 평평하게 할때에, 내가가진 가방에서 블록을 꺼내와서 채울것인지? 현재 블록을 깎고, 내가방에 한개의 블록을 넣을것인지? 를 판단하여 전체 평평화작업에 드는 최소시간을 구하는 문제이다.. 먼저 평평화작업에 대상이되는 높이는 입력으로 주어진 값의 최솟값-최댓값 사이가 될수 밖에 없다. 따라서 최소-최대값 사이의 모든 값을 반복문을 돌면서, 해당 값보다 크면 깎고, 작으면 더해주는 식으로 구현..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. � www.acmicpc.net 3차원 공간에서 모든 지점의 최소스패닝트리를 구하는 문제이다. 최악의 경우 N이 10만개일 때, 자신을 제외한 99999개를 구해야한다. 10만*10만의 연산을 통하여 간선길이를 정렬하면 메모리초과와 시간초과가나기때문에, 정렬을 통하여 m번째 노드는 m-1 , m+1번째만 계산을 통한다. ...m-2, m+2 ...은 정렬이 되어있기 때문에 최소가 보장되지 않는다. 이를 X ,Y, Z 에대해서 한..

https://www.acmicpc.net/problem/6497 6497번: 전력난 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈�� www.acmicpc.net 모든 가로등의 합에서 최소의 가로등의 비용으로 모든 노드를 연결해야하기때문에 MST문제와 동치이다. 크루스칼 알고리즘으로 해결하였다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTok..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 최소 컴포넌트의 크기가 2개가 되야 하므로, 초기 N개의 컴포넌트에서 Kruskal 알고리즘으로 성공적으로 Union되었을시, 컴포넌트의 개수를 감소시킨다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.Pri..

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 정렬 후, 투포인터를 이용해 원소의 차이를구해준다. 투포인터가 가리키는 차이가 M 을넘은경우 이후의 ii값증가는 볼필요가 없다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public c..