[문제] https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net [풀이] 문제 푸는 과정은 2가지로 크게 나뉜다. 1. union-find를 이용하여, 경로 정보를 입력받아 spanning tree를 만든다. 2. spanning tree의 부모를 체크하여, 여행 경로가 같은 경로상에 존재하는지 확인한다. 입력받은 도시의 길을 기반으로 spanning tree를 만들기 위해 union-find를 사용했다. spanning tree를 만들었으면 여행 경..
[문제] https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net [풀이] 투 포인터를 통해 풀었다. 입력되는 용액의 순서가 오름차순으로 정렬이 되어져 있는 상태이다. 그렇기 때문에 왼쪽에서 오른쪽 방향, 오른쪽에서 왼쪽으로 값을 찾아나가며, 0에 가까운 용액을 찾는다. 왼쪽을 가리키는 포인터 left, 오른쪽을 가리키는 포인터를 right라고 가정했을 경우에 용액 배열의 left위치와 right위치를 더한 값이 0보다 작다면, left를 1만큼 ..
[문제] https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net [풀이] 지름길 배열을 우선순위 큐에 저정을 한다 (시작점 기준으로) 이동한 거리를 저장해두는 배열을 고속도로의 길이 D 크기만큼 생성해준다. 이때 초기값을 아래과 같이 설정해준다. var arr = IntArray(D+1){i -> i} 우선순위 큐에서 값을 하나씩 꺼내어서 값이 없을 때까지 다음 과정을 반복한다. 1. 끝에서 시작을 뺀 거리가 지름길의 거리보다 클 경우에 아..
[문제] https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net [풀이] 동전 교환 문제라고 볼 수 있다. 이 문제를 동전 교환 문제로 표현한다면, 1원,2원,3원으로 특정 금액 만드는 경우 수를 찾아야 한다. 문제에 만들어야 하는 수의 최대는 10000이므로, 0부터 10000까지 경우를 미리 찾아놓으면 된다. 동전 교환 알고리즘은 다음은 식으로 표현이 가능하다 . 비용을 저장해 놓은 배..
https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [풀이] 다익스트라로 풀었다. [코드] import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.PriorityQueue var N = 0 var M = 0 lateinit var map : ArrayList..
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [풀이] stack을 이용하여 풀면 편하다. 왼쪽 방향으로 이동하면서 인접한 탑끼리 비교를 한다. 2가지 경우로 나눌 수 있다. 1. i번째 탑이 i-1번째 탑의 높이보다 큰 경우 이러한 경우에는 i 번째에서 레이저 신호를 보내도 i-1에서 받을수가 없다. 따라서 Pair를 이용하여, i번째의 인덱스값과 높이를 stack에 저장을 한다. 2. i번째 탑이 i-1번째 탑의 높이보다 작거나 같은 경..
