본문 바로가기

분류 전체보기282

2141. 우체국 (Python) 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 풀이 그리디에 해당하는 문제인데 모르겠어서 다른 사람의 풀이를 참고했다. 우체국의 위치를 구하려면 우체국을 세운 지점 기준으로 왼쪽에 위치한 사람의 숫자와 오른쪽에 위치한 사람의 숫자의 차가 최소가 되는 지점을 찾아야 한다. 먼저 입력으로 받은 마을 위치를 기준으로 오름차순 정렬한 후 처음부터 끝까지 우체국을 세워가며 왼쪽과 오른쪽 사람의 수를 누적합을 사용하여 체크한다. 두 누적.. 2022. 6. 4.
10282. 해킹 (Python) 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 다익스트라를 사용하여 문제를 해결할 수 있다. 입력으로 주어지는 의존성은 그래프에서 방향성이 있는 간선이라고 생각하면 된다. 예를 들어 1, 2, 3이라는 의존성이 주어지면 2번에서 1번으로 가는 비용이 3인 간선인 것이다. 예제에서 주어진 케이스 중 두 번째 케이스를 보자. 이를 그래프로 표현하면 다음과 같다. 처음에 1번 컴퓨터가 감염되어있고 의존성에 따라 다른 컴퓨터로 전염되기 시작한다. 먼저 1번 컴퓨터에서 2번 컴퓨터로 전염되는데 2초의 시간이 걸린다... 2022. 6. 3.
1082. 방 번호 (Python) 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 풀이 일단 가장 큰 숫자를 만들기 위해서는 최대한 숫자를 많이 사서 숫자의 길이를 가장 크게 해야한다. 이를 위해 가장 싼 가격을 가진 숫자를 찾아서 M원으로 총 몇 개의 숫자를 살 수 있는지를 체크한다. 이때, 숫자 0은 0 하나일 때를 제외하고 맨 앞에 오지 못하므로 1~N-1 까지의 숫자중 가장 싼 가격의 숫자를 하나 선택하여 제일 앞에 두고 다시 0~N-1 까지의 숫자 중 가장 싼 가격의 숫자를 찾아서 나머지 자리를 채운다. 이렇게 숫자를 만들고나면 M원에서 .. 2022. 6. 2.
11779. 최소비용 구하기 2 (Python) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 출발지가 주어졌고 비용에 음수가 없으므로 다익스트라를 이용하여 출발지에서 도착지까지의 최단 거리를 구할 수 있다. 다익스트라는 링크를 참고하자. 문제에서는 단순히 최단 거리뿐만 아니라 경로까지 요구하고 있다. 이를 위해 prev라는 리스트를 추가하였다. prev[x]는 출발지에서 x까지 최단 거리로 이동할 때 x 지점에 도착하기 이전에 방문했던 지점에 대한 정보를 담고 있다. 예를 들어 start -> a -> b -> x와 .. 2022. 5. 30.
14938. 서강그라운드 (Python) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이 최단거리를 활용하는 문제인데 시작점이 주어지지 않는다. 그렇기 때문에 모든 지점에서 다른 지점까지의 최단 거리를 구하는 플로이드 워셜 알고리즘을 사용하자. 플로이드 워셜 알고리즘은 링크를 참고하자. 플로이드 워셜을 사용하여 모든 지점에서 다른 지점까지의 최단 거리를 구한 후 for문을 통해서 1번부터 N번까지를 시작지점으로하여 수색범위내에 도착 가능한 지점의 아이템 개수를 카운트한다. 이중 가장 큰 값을 찾으면 된다. 코드 import sys input = sys.. 2022. 5. 30.
12851. 숨바꼭질 2 (Python) 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 bfs를 사용하여 답을 구할 수 있다. 현재 위치에서 +1, -1, *2를 해준 위치를 우선순위 큐에 넣고 시간이 빠른 것부터 큐에서 꺼내어 위의 과정을 반복한다. 방문 체크는 X위치에 도착한 시간을 사용한다. 만약 이전에 X 위치에 가장 빠른 시간 5초가 걸려 도착했는데 현재 다시 X에 도착한 시간이 6초라면 큐에 넣어주지 않는다. 하지만 4초에 도착했다면 가장 빠른 시간을 갱신하고 큐에 넣어 이동을 반복한다. 한 가지.. 2022. 5. 29.

티스토리툴바