본문 바로가기
반응형

Problem Solving/BOJ225

[BOJ][Python]1005 풀이 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net import sys; ssr = sys.stdin.readline sys.setrecursionlimit(10000) def f(node): if dp_delay[node] == -1: results = [] for child in build[node]: child_delay = f(child) results.append(child_delay) dp_delay[node] = delays[no.. 2023. 11. 24.
[BOJ][Python]17144 풀이 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net import sys; ssr = sys.stdin.readline def diffusion(ap_pos, r, c): result = [[0 for _ in range(c)] for _ in range(r)] dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)] for cur_r in range(r): for cur_c in range(c): flag = 0 if a[cur.. 2023. 11. 2.
[BOJ][Python]17070 풀이 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net import sys; ssr = sys.stdin.readline def f(cur_r, cur_c, cur_dir): global ans if cur_r == n-1 and cur_c == n-1: ans += 1 return else: if cur_dir == 0 or cur_dir == 1: if cur_c+1 < n and board[cur_r][cur_c+1] !.. 2023. 10. 30.
[BOJ][Python]15686 풀이 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net import sys; ssr = sys.stdin.readline INF = 2501 def get_chicken_distance(chicken_locations, house_locations): result = [] for house_r, house_c in house_locations: chicken_distance = INF for chick_r, chick_c in c.. 2023. 10. 27.
[BOJ][Python]14938 풀이 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net import sys; ssr = sys.stdin.readline import heapq INF = 16 n, m, r = map(int, ssr().split()) items = list(map(int, ssr().split())) routes = [[] for _ in range(n+1)] ans = 0 for _ in range(r): a, b, l = map(int, ssr().split()) .. 2023. 10. 22.
[BOJ][Python]14502 풀이 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net from collections import deque import copy import sys ssr = sys.stdin.readline def bfs(n, m, board, twos): dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)] q = deque(twos) while q: v_r, v_c = q.popleft() for dr, dc in dpos: pos_r, pos_c =.. 2023. 10. 21.
[BOJ][Python]13172 풀이 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net import sys input = sys.stdin.readline X = 1_000_000_007 # 자릿수 구분할 때 언더스코어를 사용해도 됨 def get_ni(n, x): result = 1 while x > 0: if x % 2 == 1: result = result * n % X n = n * n % X x //= 2 return result m = int(input()) ans = 0 for _ in range(m): n, s = map.. 2023. 10. 16.
[BOJ][Python]12851 풀이 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net from collections import deque n, k = map(int, input().split()) visited = [0 for _ in range(200001)] visited[n] = 1 q = deque([(n, 0)]) ans = 100001 methods = [] while q: cur_pos, cur_time = q.popleft() .. 2023. 10. 14.
[BOJ][Python]11779 풀이 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 1000000001 def dijkstra(start, end): min_costs = [INF for _ in range(n+1)] min_costs[start] = 0 min_route = [0 for _ in range(n+1)] min_route[start] =.. 2023. 10. 10.
[BOJ][Python]11054 풀이 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net def f(n, arr): dp = [1 for _ in range(n)] for i in range(n): for j in range(i): if arr[i] > arr[j]: # 현재 원소가 처음부터 비교해오는 원소보다 크면 if dp[i] < dp[j]+1: dp[i] = dp[j]+1 return dp n = int(input()) a = list(map(int, input().split())) dp = f(.. 2023. 10. 4.
반응형