본문 바로가기

전체글118

[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.
[Baekjoon-Python] 13904 : 과제 https://www.acmicpc.net/problem/13904 접근 1일에 마감일이 6일 남은 과제를 하지 않기 위해 마감일을 내림차순으로 정렬해서 마감일이 큰 것부터 점수를 구한다. 현재 날짜에 마감할 수 있는 과제까지 꺼낸다. 꺼낸 과제 중 점수가 가장 큰 과제를 구한다. 풀이 from sys import stdin from heapq import heappop, heappush n = int(stdin.readline()) task = [] for _ in range(n): d, w = map(int, stdin.readline().split()) heappush(task, (-d, w)) possible_task, score = [], 0 for day in range(-task[0][0],.. 2024. 1. 16.
[Baekjoon-Python] 2212 : 센서 https://www.acmicpc.net/problem/2212 접근 센서를 오름차순 정렬한다. 센서 사이의 거리를 구한다. 거리를 내림차순 정렬해서 앞에서 k - 1개를 뺀 나머지의 합을 구한다. 풀이 from sys import stdin n, k = int(stdin.readline()), int(stdin.readline()) sensor = sorted(map(int, stdin.readline().split())) distance = sorted([sensor[i + 1] - sensor[i] for i in range(n - 1)], reverse=True) print(sum(distance[k - 1 :])) # (1) (1) k가 2이상일 때부터 센서 사이의 거리를 줄일 수 있기 때문에.. 2024. 1. 16.

티스토리툴바