본문 바로가기

PS109

[Baekjoon-Python] 14891 : 톱니바퀴 https://www.acmicpc.net/problem/14891 접근 톱니바퀴를 데큐로 사용하여 회전하는 방향에 따라 삽입, 삭제한다. 톱니바퀴의 인덱스를 0:12시, 2:3시, 4:6시, 6:9시 두고 회전시킨 톱니바퀴부터 dfs 탐색한다. 톱니바퀴를 바로 회전시키면 조건을 만족하지 않는 톱니바퀴에 영향을 미치기 때문에 조건을 만족하는 톱니바퀴를 전부 찾은 후 한 번에 회전시킨다. 현재 톱니바퀴의 6번 인덱스가 오른쪽 톱니바퀴의 2번 인덱스와 같지 않으면 오른쪽 톱니바퀴를 반대 방향으로 회전시킨다. 현재 톱니바퀴의 2번 인덱스가 왼쪽 톱니바퀴의 6번 인덱스와 같지 않으면 왼쪽 톱니바퀴를 반대 방향으로 회전시킨다. k번 회전시킨 후 0번 인덱스가 S극이면 톱니바퀴 번호만큼 1을 왼쪽으로 shift해서.. 2024. 1. 17.
[Baekjoon-Python] 14502 : 연구소 https://www.acmicpc.net/problem/14502 접근 빈 칸 중에서 3개를 조합으로 선택해서 벽을 세운다. 바이러스를 bfs 탐색하여 빈 칸이면 전염시킨다. 빈 칸의 개수를 구한다. 풀이 from sys import stdin from itertools import combinations from collections import deque def spread(new_wall): tmp_lab = [i[:] for i in lab] for r, c in new_wall: tmp_lab[r][c] = 1 # (1) q = deque(virus) infection = 0 while q: r, c = q.popleft() infection += 1 for i in range(4): nr, .. 2024. 1. 17.
[Baekjoon-Python] 16234 : 인구 이동 https://www.acmicpc.net/problem/16234 접근 각 좌표마다 bfs 탐색하여 국경선을 열 수 있는 인접 국가 좌표를 구한다. 국경선을 연 국가들은 인구 수의 평균을 저장한다. 이전 날짜에 국경선을 연 국가만 다시 탐색하여 중복 탐색을 제거한다. 이전 날짜에 국경선을 열지 않은 국가여도 국경선을 연 국가와 인접해 있으면 현재 날짜에 다시 국경선을 열 수 있다. 풀이 from sys import stdin from collections import deque def bfs(r, c): q = deque([(r, c)]) opened = [(r, c)] tot = country[r][c] while q: r, c = q.popleft() for i in range(4): nr, nc .. 2024. 1. 17.
[Baekjoon-Python] 14500 : 테트로미노 https://www.acmicpc.net/problem/14500 접근 모든 좌표에서 dfs 탐색해서 테트로미노를 구한다. 폴리오미노가 2개일 때 3번째 폴리오미노를 더하고 2번째 좌표에서 다시 탐색해서 ㅗ, ㅏ, ㅓ, ㅜ 테트로미노를 구한다. 풀이 from sys import stdin def dfs(depth, total, r, c): global res if res >= total + (4 - depth) * max_num: # (1) return if depth == 4: # (2) res = max(res, total) return for i in range(4): nr, nc = r + direction[i], c + direction[3 - i] if is_out_of_range(nr, n.. 2024. 1. 17.
[Baekjoon-Python] 14499 : 주사위 굴리기 https://www.acmicpc.net/problem/14499 접근 주사위의 인덱스를 0:top, 1:north, 2:east, 3:west, 4:south, 5:bottom으로 두고 굴리는 방향에 따라 값을 수정한다. 풀이 from sys import stdin from collections import deque def turn(command): global dice top, north, east, west, south, bottom = dice if command == 1: # (1) dice = [west, north, top, bottom, south, east] elif command == 2: dice = [east, north, bottom, top, south, west] elif .. 2024. 1. 17.
[Baekjoon-Python] 3190 : 뱀 https://www.acmicpc.net/problem/3190 접근 큐를 뱀으로 사용한다. 풀이 from sys import stdin from collections import deque def is_out_of_range(r, c): return r = n or c = n def turn_direction(moving, i): if moving == 'L': return (i + 3) % 4 else: return (i + 1) % 4 n, k = int(stdin.readline()), int(stdin.readline()) board = [[0] * n for _ in range(n)] for _ in range(k): r, c = map(in.. 2024. 1. 17.
[Baekjoon-Python] 14503 : 로봇 청소기 https://www.acmicpc.net/problem/14503 접근 청소한 칸을 청소하지 않은 칸, 벽과 구분하기 위해 2로 저장한다. 풀이 from sys import stdin n, m = map(int, stdin.readline().split()) r, c, d = map(int, stdin.readline().split()) room = [stdin.readline().split() for _ in range(n)] direction = [(-1, 0), (0, 1), (1, 0), (0, -1)] cleaning_cnt = 1 while True: room[r][c] = '2' for _ in range(4): d = (d + 3) % 4 nr, nc = r + direct.. 2024. 1. 17.
[Baekjoon-Python] 1300 : K번째 수 https://www.acmicpc.net/problem/1300 접근 N이 최대 105이기 때문에 N x N 배열을 만들어서 풀면 1010이 소요되어 시간 초과로 해결할 수 없다. i 2024. 1. 17.
[Baekjoon-Python] 2110 : 공유기 설치 https://www.acmicpc.net/problem/2110 접근 공유기 사이의 거리를 이분 탐색한다. 1번 집에는 공유기를 무조건 설치한다. mid 거리만큼 집에 공유기를 설치했을 때 c개를 모두 설치할 수 있는지 확인한다. 풀이 from sys import stdin def binary_search(start, end): while start = bound: # (1) cnt += 1 bound = h + mid if cnt >= c: start = mid + 1 else: end = mid - 1 return end n, c = map(int, stdin.readline().split()) house = [int(stdin.readline()) for _ in range(n)] house.so.. 2024. 1. 17.
[Baekjoon-Python] 15686 : 치킨 배달 https://www.acmicpc.net/problem/15686 접근 집과 치킨집의 인덱스를 구한다. 치킨집에서 m개를 조합하여 치킨 거리를 구한다. 풀이 from sys import stdin from itertools import combinations n, m = map(int, stdin.readline().split()) house = [] chicken = [] for i in range(n): city = list(map(int, stdin.readline().split())) for j in range(n): if city[j] == 1: house.append((i, j)) elif city[j] == 2: chicken.append((i, j)) res = 1e9 for chicke.. 2024. 1. 17.

티스토리툴바