Door

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 그리디 문제입니다. 만약에 날짜가 겹친다면 가격을 더 쌘데 부르는 곳을 가야합니다. 이 문제는 우선순위 큐로 풀 수 있었습니다. q에 페이를 넣어주되 현재 날짜가 q보다 크면 q의 가장 작은 값을 pop해줍니다. 예를들면 1 20 1 100 이렇게 들어왔다고 치면 1 100을 넣으면 q가 20 100 이렇게 2개가 됩니다. 그런데 day==1이므로 q의 길이가 ..

알고리즘 공부 2022. 9. 20. 22:33

https://www.acmicpc.net/problem/2141 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 이 문제는 처음 마주하면 '어라?쉬운데?'하다가 제출하는 순간 ???이게 뭐지?? 하게 되는 문제. 이 문제에서 대부분의 사람이라면 '각 사람들까지 거리합이 최소'라는 말에 유의합니다. 그래서 최소지점을 '(현재 마을위치-지금 마을위치)x(지금마을 인구)' 이렇게 거리를 구한 뒤 이게 최소가 되는 지점을 찾을 것입니..

알고리즘 공부 2022. 9. 20. 17:42

https://www.acmicpc.net/problem/18224 18224번: 미로에 갇힌 건우 건우가 가장 빨리 탈출할 수 있는 날이 몇번째 날인지, 그리고 낮이면 "sun", 밤이면 "moon"을 공백으로 구분하여 함께 출력한다. 예를 들어, 2번째 날 밤일 경우, "2 moon" 을 출력하고, 3번째 날 낮 www.acmicpc.net bfs문제 중에서 '조건'이 정말 까다롭게 붙은 유형. 이 문제를 봤을 때 가장 어려운 부분은 'm만큼 이동하면 낮과 밤이 바뀐다'라는 부분. 문제를 잘 읽어보면 이동하는 순간에 바뀝니다. 예를들며 m=2인데 낮 1 이라면 이동하는 순간 2가 되어서 밤 0으로 바뀌는 것. 사실 여기까지만 알면 문제가 안풀립니다. 게시판의 반례에 계속 넣어보는데 문제가 안풀렸습니다..

알고리즘 공부 2022. 9. 19. 17:44

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 이 문제는 까다로운 지점이 많습니다. 우선, 그림으로 이 문제에서 봐야할 걸 보겠습니다. 바로 방문한 곳을 다시 갈 수 있는 점입니다. 조건에 불켜진 곳만 방문할 수 있다고 적혀있습니다. 그래서 처음에는 가지 못하는 곳이 다른 곳을 방문하면서 스위치를 키면 방문이 가능해집니다. 그런데 bfs를 구현하다보면 '한번 방문한 곳은 다시 방문하지 않는..

알고리즘 공부 2022. 9. 19. 14:20

https://www.acmicpc.net/problem/22868 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 그래프+bfs에 대한 개념이 있으면 풀 수 있는 문제. 시작->도착 도착->시작 두 사이의 bfs를 구해서 이동거리를 구하면 됩니다. 그런데, 이 문제에서 구현해야 할 것이 하나 있습니다. 바로 '이미 갔던 지점은 가지 않는다'라는 조건. 시작->도착에서 갔던 지점은 도착->시작에서는 갈 수 없습니다. 예를들면 1,2,3,4,5 까지 길이 있고 1->3까지 간다고 ..

알고리즘 공부 2022. 9. 19. 09:53

https://www.acmicpc.net/problem/1724 1724번: 그림판 첫 행에는 그림판의 세로 방향 크기 N과 가로 방향 크기 M이 공백으로 구분되어 주어진다. (1

알고리즘 공부 2022. 9. 18. 13:31

https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제는 워낙 심플한데 풀이는 심플하지 않았던 문제. 제가 처음 틀렸던 풀이를 먼저 보겠습니다. #백준 1981 배열에서 이동 #틀린풀이 from heapq import heappop,heappush from copy import deepcopy dx=[0,0,1,-1] dy=[1,-1,0,0] N=int(input()) room=[] ma_val=0 mi_val=1e9 fo..

알고리즘 공부 2022. 9. 18. 11:42

https://www.acmicpc.net/problem/2931 2931번: 가스관 www.acmicpc.net 문제를 보면 당황스럽지만 하나씩 접근해보면 괜찮은 문제. 주의사항을 말하면 M과 Z 둘 중 하나는 움직여야합니다. M을 기준으로 움직인다했을때 M 근처의 파이프가 사라져서 M이 움직이지 못하는 경우가 생겨서 M이 움직이지 못합니다. 그러니 M과 Z 둘 중 하나를 움직이도록 설정해주세요. 움직이고 나서 끊어진 좌표가 있습니다. 그 해당 좌표가 바로 M과 Z사이를 잇는 좌표죠. 그 다음에는 동서남북으로 해당 좌표기준으로 어떤 트랙이 있는지 구합니다. 예를들면 해당 트렉근처로 남과 북에 길이 있다면 | 도로가 있으면 되고 동 북에 길이 있다면 2를 반환하면 됩니다. (이 부분은 구글링으로 힌트를 ..

알고리즘 공부 2022. 9. 17. 22:16