본문 바로가기
728x90

알고리즘316

[python] 백준 20055 컨베이어 벨트 위의 로봇 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 해결 문제에서 주어진 패턴을 몇 번 반복하는지 구하는 문제. 회전을 하므로 stack이 아닌 que를 이용해야하므로 파이썬에선 deque를 이용한다. container 안에 리스트를 만들어 로봇이 있으면 0을 추가적으로 넣어 이동시키는 것을 구현한다. index가 n-1일 때 로봇이 있으면 언제든지 빼주도록 한다.(실수로 넘어가면 안된다...) pypy3로 통과. 아무래.. 2023. 6. 22.
[python] 백준 19238 스타트 택시 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 해결 정해진 출발지에서 가장 가까이 있는 사람(같은 거리에 있으면 행이 작은 위치,열이 작인 위치 순으로 있는 사람)을 픽업한 다음 그 사람의 목적지에 도달시키면서 이동하면서 남은 연료를 출력하는 문제이다.(부족하면 -1) 따라서 출발지에서부터 각 위치의 최단 거리를 구한다음 가장 작은 사람을 픽업하러 간 후 그 위치에서 (정해진)목적지까지 거리를 계산.. 2023. 6. 22.
[python] 백준 11758 CCW https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 문제 해결 CCW(Counter-Clockwise)를 알면 쉬운 문제. 외적과 관련되어있는데 외적에서 절대값을 없앤 $(X_{1}Y_{2}+X_{2}Y_{3}+X_{3}Y_{1})-(X_{2}Y_{1}+X_{3}Y_{2}+X_{1}Y_{3})$의 부호에 따라 벡터가 움직이는 방향이 다르다는 것이다. $(X_{1}Y_{2}+X_{2.. 2023. 6. 14.
[python] 백준 17822 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제 해결 원판을 돌리는 코드를 짤 수 있어야한다.(시계방향과 반시계방향 2가지 나눠서) X가 되어 사라진 것은 0으로 표시한다.(없애는 것은 BFS를 통해 한번에 없앤다.) 변화가 없을 때는 평균을 구해서 0이상의 수중 평균보다 작은 것은 +1 큰 것은 -1을 계산해준다. CODE from collections import deque def bfs(x, y): global fla.. 2023. 6. 7.
728x90