본문 바로가기

PS109

[Baekjoon-Python] 17779 : 게리맨더링 2 https://www.acmicpc.net/problem/17779 접근 x, y 좌표에 따라 경계의 길이 d1, d2를 1씩 증가시키며 경계선을 그린다. 1 ~ 4번 선거구별 인구 수를 구한다. 5번 선거구의 인구 수는 총 인구 수에서 1 ~ 4번 선거구별 인구 수의 합을 뺀다. 풀이 from sys import stdin def get_wards(r, c, d1, d2) -> list: wards = [0] * 5 boundary = draw_boundary(r, c, d1, d2) wards[0] = sum_ward(boundary, 0, r + d1, 0, c + 1, 1, 1) # (1) wards[1] = sum_ward(boundary, 0, r + d2 + 1, n - 1, c, 1, -1.. 2024. 1. 21.
[Baekjoon-Python] 1946 : 신입 사원 https://www.acmicpc.net/problem/1946 접근 서류 성적 순위를 인덱스로 사용한다. 인덱스를 순회하면서 면접 성적 순위를 비교한다. 풀이 from sys import stdin for _ in range(int(stdin.readline())): n = int(stdin.readline()) interview_rank = [0] * n for _ in range(n): a, b = map(int, stdin.readline().split()) interview_rank[a - 1] = b - 1 # (1) min_interview_rank = interview_rank[0] # (2) cnt = 1 # (3) for rank in interview_rank[1:]: # (4) i.. 2024. 1. 21.
[Baekjoon-Python] 2493 : 탑 https://github.com/co-niverse/algorithm-study/pull/111 접근 스택 맨 위의 탑보다 현재 탑의 높이가 더 높으면 높이가 작거나 같을 때까지 스택을 삭제한다. 스택 맨 위의 탑보다 현재 탑의 높이가 작거나 같으면 스택 맨 위의 탑의 인덱스를 저장한다. 스택에 현재 탑을 삽입한다. 풀이 from sys import stdin n = int(stdin.readline()) res = [0] * n stack = [] for i, height in enumerate(map(int, stdin.readline().split())): if stack and stack[-1][0] < height: # (1) while stack and stack[-1][0] < height.. 2024. 1. 21.
[Baekjoon-Python] 17825 : 주사위 윷놀이 https://www.acmicpc.net/problem/17825 접근 게임판을 아래와 같이 설정한다. r = 0: 10, 20, 30에 말이 놓이지 않았을 때 이동하는 칸이다. r = 1: r = 0에서 10에 말이 놓였을 때 이동하는 칸이다. r = 2: r = 0에서 20에 말이 놓였을 때 이동하는 칸이다. r = 3: r = 0에서 30에 말이 놓였을 때 이동하는 칸이다. r = 4: r = 0, 1, 2, 3, 5에서 40에 말이 놓였을 때 이동하는 칸이다. r = 5: r = 1, 2, 3에서 25, 30, 35에 말이 놓였을 때 이동하는 칸이다. 말이 이동한 좌표에 따라 게임판의 인덱스를 조정하고 dfs 탐색한다. 풀이 from sys import stdin def dfs(i, record.. 2024. 1. 21.
[Baekjoon-Python] 1446 : 지름길 https://www.acmicpc.net/problem/1446 접근 도로 길이를 순회하면서 현재 운전거리의 최솟값을 메모이제이션한다. 지름길을 지나지 않는 것이 거리가 더 짧을 수 있다. 현재 위치가 지름길 도착 위치와 같다면 지름길을 지나서 온 거리와 현재 값 중 작은 것을 선택한다. 풀이 from sys import stdin n, d = map(int, stdin.readline().split()) short_road = [tuple(map(int, stdin.readline().split())) for _ in range(n)] dp = [1e9] * (d + 1) dp[0] = 0 for i in range(1, d + 1): dp[i] = dp[i - 1] + 1 for start, end.. 2024. 1. 21.
[Baekjoon-Python] 21608 : 상어 초등학교 https://www.acmicpc.net/problem/21608 접근 입력받은 학생 번호 순서로 자리를 지정한다. 교실을 순회하면서 상하좌우를 확인한다. 상하좌우에 좋아하는 학생이 가장 많은 자리를 찾는다. 좋아하는 학생이 가장 많은 자리가 여러 개이면 상하좌우에 빈 칸이 많은 자리를 찾는다. 행, 열을 오름차순으로 순회하기 때문에 빈 칸이 많은 자리가 여러 개여도 가장 먼저 찾은 자리가 행, 열 번호가 가장 작다. 풀이 from sys import stdin def sit(my_favorite): now_r = now_c = -1 max_my_favorite_cnt = max_blank_cnt = 0 for r in range(n): for c in range(n): if classroom[r][c.. 2024. 1. 21.
[Baekjoon-Python] 1918 : 후위 표기식 https://www.acmicpc.net/problem/1918 접근 여는 괄호와 연산자는 스택에 삽입한다. 여는 괄호는 닫는 괄호를 만났을 때 스택에서 삭제한다. 연산자는 다음 연산자보다 우선순위가 높을 때 스택에서 삭제한다. 풀이 from sys import stdin infix = stdin.readline().rstrip() priority = {"*": 2, "/": 2, "+": 1, "-": 1} stack = [] res = [] for token in infix: if 65 = priority[token]: res.append(stack.pop()) stack.append(token) while stack: res.append(stack.pop()) # (6) print("".join(.. 2024. 1. 21.
[Baekjoon-Python] 14719 : 빗물 https://www.acmicpc.net/problem/14719 접근 블록을 순회하면서 현재 블록 기준 왼쪽에서 가장 높은 높이, 오른쪽에서 가장 높은 높이를 구한다. 두 높이 중 최솟값까지 물이 고일 수 있다. 풀이 from sys import stdin h, w = map(int, stdin.readline().split()) blocks = list(map(int, stdin.readline().split())) res = 0 for i in range(1, w - 1): # (1) left = max(blocks[:i]) # (2) right = max(blocks[i + 1 :]) # (3) min_height = min(left, right) # (4) if min_height > bloc.. 2024. 1. 21.
[Baekjoon-Python] 1107 : 리모컨 https://www.acmicpc.net/problem/1107 접근 최대로 버튼을 누른 횟수는 + 또는 - 버튼만 사용한 횟수이다. 숫자 버튼을 눌러 어떤 채널로 이동한 후 + 또는 - 버튼으로 이동하려는 채널에 도달할 수 있다. 채널은 무한대이기 때문에 탈출 조건이 없으면 무한 루프에 빠진다. 풀이 from sys import stdin def check_button(limit, next): move_cnt = res channel = 100 while channel != limit: for num in str(channel): if num in broken: # (1) break else: move_cnt = min(move_cnt, len(str(channel)) + abs(channel - n.. 2024. 1. 21.
[Baekjoon-Python] 21610 : 마법사 상어와 비바라기 https://www.acmicpc.net/problem/21610 접근 격자의 끝이 연결되어 있기 때문에 구름이 이동할 때 n으로 나눈 나머지만큼 이동한다. 이동한 구름 좌표를 저장해서 물복사버그를 사용할 때 좌표의 대각선을 순회하고, 새로운 구름을 생성할 때 좌표가 포함되었는지 확인한다. 풀이 from sys import stdin from collections import deque def move_cloud(move_r, move_c) -> set: moved_cloud = set() while cloud: r, c = cloud.popleft() r, c = (r + move_r) % n, (c + move_c) % n # (1) board[r][c] += 1 moved_cloud.add((r,.. 2024. 1. 21.

티스토리툴바