PS109 [Baekjoon-Python] 20057 : 마법사 상어와 토네이도 https://www.acmicpc.net/problem/20057 접근 비율이 적힌 칸의 인덱스를 미리 계산한다. 토네이도는 x번 전진을 두 번하면 x + 1번 전진한다. y의 모래를 비율이 적힌 칸으로 모두 이동시킨 후에 남은 모래를 알파로 이동시킨다. 풀이 from sys import stdin from math import floor def tornado(r, c, d): over_amount = 0 sand, board[r][c] = board[r][c], 0 dr, dc = direction[d] tmp = 0 for i in range(9): # (1) pr, pc = p_direction[d][i] moved_sand = floor(sand * percent[i]) if is_out_of_.. 2024. 1. 23. [Baekjoon-Python] 19238 : 스타트 택시 https://www.acmicpc.net/problem/19238 접근 bfs 탐색하여 택시 좌표에서 각각의 영역까지 거리를 구한다. 가장 가까운 승객 좌표를 찾는다. bfs 탐색하여 승객 좌표에서 목적지까지의 거리를 구한다. 연료가 충분하면 택시의 좌표를 승객의 목적지로 변경한다. 택시 -> 승객 출발지 연료 감소, 승객 출발지 -> 승객 목적지 연료 감소, 목적지에 도착하면 출발지에서 목적지까지 소모한 연료의 두 배만큼 연료 증가 풀이 from sys import stdin from collections import deque def bfs(start_r, start_c): # (1) visited = [[-1] * n for _ in range(n)] q = deque([(start_r, star.. 2024. 1. 23. [Baekjoon-Python] 1765 : 닭싸움 팀 정하기 https://www.acmicpc.net/problem/1765 접근 유니온-파인드를 사용하여 인간관계를 합친다. 풀이 from sys import stdin def find(x): if x != friend[x]: friend[x] = find(friend[x]) return friend[x] def union(a, b): a, b = find(a), find(b) if a == b: return friend[b] = a n, m = int(stdin.readline()), int(stdin.readline()) friend = [i for i in range(n + 1)] enemy = [[] for _ in range(n + 1)] for _ in range(m): letter, p, q = st.. 2024. 1. 23. [Baekjoon-Python] 1106 : 호텔 https://www.acmicpc.net/problem/1106 접근 최소 비용을 메모이제이션한다. dp의 인덱스를 고객 수로 설정한다. 풀이 from sys import stdin c, n = map(int, stdin.readline().split()) city = [list(map(int, stdin.readline().split())) for _ in range(n)] dp = [1e9] * (c + 1) # (1) dp[0] = 0 for i in range(1, c + 1): for cost, customer in city: if i 2024. 1. 23. [Baekjoon-Python] 4179 : 불! https://www.acmicpc.net/problem/4179 접근 불과 지훈 좌표를 따로 저장한다. 해당 분동안 불을 먼저 bfs로 확산한 후 지훈을 bfs 탐색한다. 풀이 from sys import stdin from collections import deque def escape(): maze[jihoon[0][0]][jihoon[0][1]] = -1 minutes = 0 while jihoon: minutes += 1 spread_fire() for _ in range(len(jihoon)): # (1) r, c = jihoon.popleft() for i in range(4): nr, nc = r + direction[i], c + direction[3 - i] if is_out_of_ra.. 2024. 1. 23. [Baekjoon-Python] 1509 : 팰린드롬 분할 https://www.acmicpc.net/problem/1509 접근 팰린드롬은 거꾸로 읽어도 제대로 읽은 것과 같은 문장을 의미한다. 현재 문자열의 시작 문자와 끝 문자가 같고 내부 문자열이 팰린드롬이면 현재 문자열은 팰린드롬이다. 풀이 from sys import stdin letter = stdin.readline().rstrip() n = len(letter) palindrome = [[0] * n for _ in range(n)] dp = [2500] * (n + 1) dp[-1] = 0 for e in range(n): for s in range(e + 1): if letter[s] == letter[e] and (e - s < 2 or palindrome[s + 1][e - 1]): # (.. 2024. 1. 23. [Baekjoon-Python] 1717 : 집합의 표현 https://www.acmicpc.net/problem/1717 접근 유니온-파인드를 사용하여 두 집합을 합친다. 풀이 from sys import stdin, setrecursionlimit def find(x): if x != parent[x]: parent[x] = find(parent[x]) return parent[x] def union(a, b): a = find(a) b = find(b) if a < b: parent[b] = a else: parent[a] = b setrecursionlimit(10**6) n, m = map(int, stdin.readline().split()) parent = [i for i in range(n + 1)] for _ in range(m): operat.. 2024. 1. 23. [Baekjoon-Python] 2468 : 안전 영역 https://www.acmicpc.net/problem/2468 접근 비의 양을 0 ~ 지역의 최고 높이 - 1까지 순회하면서 안전한 영역의 개수를 구한다. 안전한 영역은 bfs 탐색한다. 풀이 from sys import stdin from collections import deque def bfs(r, c, rain, q: deque): q.append((r, c)) while q: r, c = q.popleft() for i in range(4): nr, nc = r + direction[i], c + direction[3 - i] if is_out_of_range(nr, nc) or visited[nr][nc] or city[nr][nc] = n or c = n n = int(.. 2024. 1. 23. [Baekjoon-Python] 20437 : 문자열 게임 2 https://www.acmicpc.net/problem/20437 접근 알파벳의 ASCII - 97을 인덱스로 사용한다. 알파벳마다 문자열의 인덱스를 저장한다. 알파벳을 순회하면서 k개 포함하는 인덱스 2개를 찾고, 문자열의 길이를 구한다. 최소 길이, 최대 길이를 갱신한다. 풀이 from sys import stdin def play(): min_len, max_len = 1e9, 0 for alpha in alphabet: if len(alpha) < k: # (1) continue for i in range(len(alpha) - k + 1): length = alpha[i + k - 1] - alpha[i] + 1 # (2) if length < min_len: min_len = length i.. 2024. 1. 23. [Baekjoon-Python] 20061 : 모노미노도미노 2 https://www.acmicpc.net/problem/20061 접근 새로운 행은 앞에서 추가되고 0, 1행에 블록이 존재할 때 뒤부터 삭제되기 때문에 데큐를 사용한다. blue는 x를 열로 두고 green과 같이 진행한다. 열이 가득 찬 행을 먼저 삭제하고 0, 1행을 확인한다. 풀이 from sys import stdin from collections import deque def find_top(board, c): # (1) for r in range(2, 6): # (2) if board[r][c] == 1: return r - 1 return 5 def remove_full_col(): global res for board in blue, green: for r in range(2, 6): .. 2024. 1. 23. 이전 1 2 3 4 5 6 7 ··· 11 다음
