본문 바로가기

전체 글282

17071. 숨바꼭질 5 (Python) 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 시간 제한이 0.25초로 빡빡하기 때문에 일반적인 방문체크로는 정답을 구할 수 없다. 이때 필요한 것이 짝수초와 홀수초로 나누어 방문 체크를 하는 것이다. 예를 들어 수빈이가 10의 위치에 2초에 도착했다고 가정해보자. 수빈이는 X-1이나 X+1을 이동할 수 있다. 즉, 10에서 왼쪽으로 한 번 이동하고 오른쪽으로 한 번 이동하는 방식으로 다시 같은 위치로 이동할 수 있다. 10의 위치에 2 + 2초, 2 + 4초, 2 .. 2022. 6. 9.
17136. 색종이 붙이기 (Python) https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 1이 적힌 칸에서 1x1 크기의 색종이부터 5x5 크기의 색종이까지 붙일 수 있는지를 체크한다. 색종이를 붙이고 나면 색종이로 덮어진 부분을 체크해주고 다음 1이 적힌 칸으로 넘어가서 색종이를 붙일 수 있는지를 체크하는 과정을 반복한다. 모든 1이 적힌 칸을 색종이로 덮고 나면 사용한 색종이의 개수들을 비교하여 그 중 최소 개수를 기록하면 된다. 코드 # size * size 색종이.. 2022. 6. 7.
2240. 자두나무 (Python) 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 3차원 dp 배열을 이용하여 문제를 해결할 수 있다. 3차원 dp 정보는 다음과 같다. dp[t][w][p] : t시간에 w번 이동하여 p번 나무에 있을 때 받을 수 있는 자두의 최대 개수 처음에는 1번 자두 나무에 위치하므로 이에 대하여 따로 처리해준다. 만약 처음으로 떨어지는 자두의 위치가 1일 경우에는 이동하지 않고 자두를 받을 수 있으므로 dp[1][0][1]을 1로 설정한다. 처음으로 떨어지는 자두의 위치가 2일 경우에는 한 번 이동해야 받을 수 있으므로 .. 2022. 6. 6.
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.

티스토리툴바