본문 바로가기

PS109

[Baekjoon-Python] 1916 : 최소비용 구하기 https://www.acmicpc.net/problem/1916 접근 다익스트라 알고리즘을 사용하여 출발 도시에서 도착 도시까지 가는데 발생하는 최소 비용을 구한다. 풀이 from sys import stdin from heapq import heappop, heappush def dijkstra(start): q = [] heappush(q, (0, start)) while q: dist, now = heappop(q) if now == end: # (1) break for next, next_dist in city[now].items(): next_dist += dist if next_dist < distance[next]: distance[next] = next_dist heappush(q, (n.. 2024. 1. 21.
[Baekjoon-Python] 20055 : 컨베이어 벨트 위의 로봇 https://www.acmicpc.net/problem/20055 접근 벨트는 2N 길이의 큐, 로봇은 N길이의 큐로 사용한다. 풀이 from sys import stdin from collections import deque def put_robot(idx): global durability robot[idx] = True belt[idx] -= 1 if belt[idx] == 0: durability += 1 n, k = map(int, stdin.readline().split()) belt = deque(map(int, stdin.readline().split())) robot = deque([False] * n) step, durability = 0, 0 while durability < k: .. 2024. 1. 21.
[Baekjoon-Python] 17140 : 이차원 배열과 연산 https://www.acmicpc.net/problem/17140 접근 Counter 클래스를 사용하여 등장 횟수를 구한다. C 연산은 열을 행으로 변환해서 정렬하고 다시 열로 변환한다. 풀이 from sys import stdin from collections import Counter def sort(array): res, max_len = [], 0 for arr in array: counter = Counter(arr) # (1) counter.pop(0, None) # (2) row = sorted(counter.items(), key=lambda x: (x[1], x[0])) # (3) row = list(sum(row, ())) # (4) if len(row) > 100: # (5) row.. 2024. 1. 21.
[Baekjoon-Python] 16236 : 아기 상어 https://www.acmicpc.net/problem/16236 접근 bfs 탐색하여 물고기를 찾는다. 상어보다 크기가 작은 물고기를 찾으면 거리와 물고기 좌표를 저장한다. 빈 칸이거나 상어와 크기가 같다면 이동한다. 먹을 수 있는 물고기가 여러 마리라면 거리가 가장 가까운 물고기를, 거리가 가장 가까운 물고기가 여러 마리라면 행이 가장 작은 물고기를, 행이 가장 작은 물고기가 여러 마리라면 열이 가장 작은 물고기를 먹는다. 풀이 from sys import stdin from collections import deque def bfs(r, c): q = deque([(0, r, c)]) visited = [[False] * n for _ in range(n)] visited[r][c] = True .. 2024. 1. 21.
[Baekjoon-Python] 14890 : 경사로 https://www.acmicpc.net/problem/14890 접근 행과 열을 구분하여 두 번 순회한다. 높이 차이가 2 이상이면 경사로를 놓을 수 없다. 경사로를 놓았을 때 방문 처리하여 경사로가 겹치는 경우를 확인한다. 풀이 from sys import stdin def can_move(road): slope = [False] * N i = 1 while i 1: # (1) return False if road[i - 1] > road[i]: # (2) for j in range(i, i + L): if j >= N or road[j] != road[i]: return False slope[j] = True i += L elif .. 2024. 1. 20.
[Baekjoon-Python] 16926 : 배열 돌리기 1 https://www.acmicpc.net/problem/16926 접근 함께 회전하는 배열을 계층이라고 할 때, 각 계층을 순회한다. 계층의 총 개수는 min(n, m) / 2이다. i번째 계층의 시작 좌표 (x, y)는 (i , i)이다. (i , i)부터 반시계 방향으로 i번째 계층의 값을 큐에 삽입한다. 큐를 r만큼 회전한 후 큐에서 값을 삭제하면서 (i , i)부터 반시계 방향으로 값을 저장한다. 풀이 from sys import stdin from collections import deque n, m, r = map(int, stdin.readline().split()) arr = [stdin.readline().split() for _ in range(n)] q = deque() for i .. 2024. 1. 20.
[Baekjoon-Python] 14501 : 퇴사 https://www.acmicpc.net/problem/14501 접근 날짜를 역순으로 순회하면서 해당 날짜 수익의 최댓값을 메모이제이션한다. 현재 날짜의 수익은 현재와 T일 뒤의 수익의 합, 다음날의 수익 중 최댓값이다. 즉, 오늘 상담해서 T일 뒤에 상담할 것인지, 오늘 상담을 포기하고 내일 상담할 것인지 선택하는 것이다. 풀이 from sys import stdin n = int(stdin.readline()) consulting = [tuple(map(int, stdin.readline().split())) for _ in range(n)] dp = [0] * (n + 1) for d in range(n - 1, -1, -1): # (1) t, p = consulting[d] if d + t >.. 2024. 1. 20.
[Baekjoon-Python] 15685 : 드래곤 커브 https://www.acmicpc.net/problem/15685 접근 0:우, 1:상, 2:좌, 3:하로 방향 인덱스를 정한다. k세대 드래곤 커브의 방향은 k - 1세대 드래곤 커브의 방향을 역순으로 순회하면서 1씩 증가한다. 풀이 from sys import stdin dragon = [[False] * 101 for _ in range(101)] direction = [(0, 1), (-1, 0), (0, -1), (1, 0)] for _ in range(int(stdin.readline())): x, y, d, g = map(int, stdin.readline().split()) dragon[y][x] = True # (1) y += direction[d][0] x += direction[d].. 2024. 1. 20.
[Baekjoon-Python] 15684 : 사다리 조작 https://www.acmicpc.net/problem/15684 접근 각각의 세로선마다 놓여진 가로선 개수가 홀수이면 원래 세로선으로 돌아올 수 없다. 즉, 세로선마다 놓여진 가로선 개수가 모두 짝수여야 한다. 세로선을 dfs 탐색해서 가로선이 놓여있지 않으면 가로선을 추가한다. 추가한 가로선 개수가 3개보다 많아질 경우 백트래킹한다. 풀이 from sys import stdin def is_same_vertical(): # (1) for j in range(1, n + 1): start = j for i in range(1, h + 1): if ladder[i][j]: j = ladder[i][j] if start != j: return False return True def dfs(cnt, dep.. 2024. 1. 18.
[Baekjoon-Python] 15683 : 감시 https://www.acmicpc.net/problem/15683 접근 각각의 cctv마다 감시할 수 있는 경우의 수 cctv 경우의 수 1번 4 2번 2 3번 4 4번 4 5번 1 cctv를 dfs 탐색해서 감시할 수 있는 모든 경우의 수를 구한다. 탐색이 끝나면 사각 지대의 크기를 구한다. 풀이 from sys import stdin def dfs(office, idx): global res if idx >= len(cctv): blind_spot = sum(o.count(0) for o in office) res = min(res, blind_spot) # (1) return r, c = cctv[idx] if office[r][c] == 1: # (2) for i in range(4): tmp_.. 2024. 1. 17.

티스토리툴바