문제https://www.acmicpc.net/problem/1027 1027: 고층 건물세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.www.acmicpc.net해설현재 건물 [i]를 기준으로 왼쪽을 봤을 때 보이는 건물의 개수 + 오른쪽을 봤..
문제https://www.acmicpc.net/problem/14466 14466: 소가 길을 건너간 이유 6소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.www.acmicpc.net해설일반 BFS를 수행하면길을 이용하지 않으면 돌아가야하는 경우 vs 길을 이용하면 더 빨리 도달할 수 있는 경우위의 상황에 길을 무조건 타는 것이 최소경로이므로 길을 타게 되어 틀린 답을 내놓게 된다고 생각함.따라서, PQ를 통해 Info객체의 compareTo를 재정의하여 Info의 멤버변수인 isRoad(길을 사용한적 있는지)에 따라 이용한적 없는 객체를 우선순위를 높힘또한, 소 a, b, c, d, e가 있을 때 문제는 쌍 의 개수를 구..
문제https://www.acmicpc.net/problem/16166 16166: 서울의 지하철한국에 처음 도착한 미국인 Mr.Goofcode는 한국의 수도 서울을 여행할 생각에 들떠 있었다. 하지만, 공항 철도를 타고 서울역에 도착한 Mr.Goofcode는 복잡한 서울의 지하철 노선도를 보고 경악을 금치 못했다. 왜냐하면, 서울역을 포함한 서울의 모든 역은 이름이 아닌 숫자로 구분해야 했으며, 운영되는 지하철의 종류(호선)가 너무 많아 최적의 이동 경로를 계산하기 어려웠기 때문이다.www.acmicpc.net해설Map에 역번호, List 형식으로 해당 역에서 갈 수 있는 모든 역 (다른 호선도 가능)을 저장Edge는 호선, v -> u 의 정보 저장Info는 호선, 역, 환승 횟수, isv역할의 Se..
문제https://www.acmicpc.net/problem/13913 13913: 숨바꼭질 4수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.www.acmicpc.net해설기존 숨바꼭질 시리즈 문제와 동일하게 해결했다.BFS를 통해 몇번만에 도달했는지를 DP에 저장한다.최종적으로 K에 도달하는 경우는 가장 먼저 도달한 1가지 경우뿐이다.또한, 이는 K라는 목적지에 도달하기 위해 선행되어야 하는 위치는 1개..
문제https://www.acmicpc.net/problem/1092 1092: 배지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.www.acmicpc.net해설처음에는 그냥 PQ에 넣고 하나씩 확인하며 안넣어지면 Queue에 넣고 다음 탐색을 해보는 식으로 시뮬레이션? 형식으로 풀었는데 메모리 초과가 났다(반례 : (1.....1,2), (2......2,2))인 경우 하나만 되고 끝까지 안되는데 모두 확인 N * M개를 큐에 넣게 되기 때문에 메모리 초과가 발생따라서, 이분 탐색을 통해 크래인이 들 수 있는 무게를 target으로 하여 상자의 무게..
