본문 바로가기

전체글118

[Baekjoon-Python] 17837 : 새로운 게임 2 https://www.acmicpc.net/problem/17837 접근 턴마다 1번 말부터 순서대로 이동한다. 체스판 한 칸에 여러 말이 존재할 수 있기 때문에 리스트를 사용한다. 말을 위에서부터 꺼내면 뒤집한 상태가 된다. 다음 칸이 흰색이면 다시 뒤집고 빨간색이면 뒤집지 않는다. 풀이 from sys import stdin def move(): direction = [(0, 1), (0, -1), (-1, 0), (1, 0)] turn_cnt = 1 while turn_cnt < 1001: for i in range(k): r, c, d = pieces[i] nr, nc = r + direction[d][0], c + direction[d][1] if is_out_of_range(nr, nc) or.. 2024. 1. 22.
[Baekjoon-Python] 23288 : 주사위 굴리기 2 https://www.acmicpc.net/problem/23288 접근 지도를 bfs 탐색하여 연속해서 이동할 수 있는 좌표를 구한 후 점수를 미리 계산해서 중복을 제거한다. 주사위의 인덱스를 0:top, 1:north, 2:east, 3:west, 4:south, 5:bottom으로 두고 굴리는 방향에 따라 주사위 면을 재구성한다. 풀이 from sys import stdin from collections import deque def bfs(r, c) -> set: # (1) q = deque([(r, c)]) same_scores = {(r, c)} while q: r, c = q.popleft() for d in direction: nr, nc = r + d[0], c + d[1] if is_o.. 2024. 1. 21.
[Baekjoon-Python] 2294 : 동전 2 https://www.acmicpc.net/problem/2294 접근 가치를 순회하면서 동전 개수의 최솟값을 메모이제이션한다. 풀이 from sys import stdin n, k = map(int, stdin.readline().split()) coins = set() # (1) for _ in range(n): coin = int(stdin.readline()) if coin = coin: # (3) dp[v] = min(dp[v], dp[v - coin] + 1) print(dp[k] if dp[k] != 1e9 else -1) (1) 가치가 같은 동전이 여러 번 주어질 수 있기 때문에 set을 사용한다. (2) k보다 작거나 같은 동전만 삽입한다. (3) 현재 동전이 가치보다 작거나 같으면 최솟.. 2024. 1. 21.
[Baekjoon-Python] 17142 : 연구소 3 https://www.acmicpc.net/problem/17142 접근 바이러스 중 m개의 활성 바이러스를 조합으로 선택한다. bfs 탐색하면서 바이러스를 퍼뜨린다. 빈 칸의 개수가 0이면 최소 시간을 갱신한다. 풀이 from sys import stdin from collections import deque from itertools import combinations def bfs(virus, empty_cnt) -> int: q = deque(virus) visited = [[0] * n for _ in range(n)] for r, c in virus: # (1) visited[r][c] = 1 while q: r, c = q.popleft() for i in range(4): nr, nc = .. 2024. 1. 21.
[Baekjoon-Python] 2178 : 미로 탐색 https://www.acmicpc.net/problem/2178 접근 미로를 bfs 탐색한다. 풀이 from sys import stdin from collections import deque def bfs(x, y): q = deque([(x, y, maze[x][y])]) while q: r, c, cnt = q.popleft() cnt += 1 for i in range(4): nr, nc = r + direction[i], c + direction[3 - i] if is_out_of_range(nr, nc): continue if maze[nr][nc] == 0 or maze[nr][nc] > cnt: # (1) maze[nr][nc] = cnt q.append((nr, nc, cnt)) def.. 2024. 1. 21.
[Baekjoon-Python] 21758 : 꿀 따기 https://www.acmicpc.net/problem/21758 접근 꿀의 누적합을 구한다. 벌 또는 벌통은 양 끝에 위치해야 한다. 벌, 벌, 벌통, 벌, 벌통, 벌, 벌통, 벌, 벌 세 가지 경우의 수를 확인하고 최대의 꿀의 양을 구한다. 풀이 from sys import stdin def fly(): honey_amount = 0 for i in range(1, n - 1): # (1) bee_1 = accum_honey[n - 1] - honey[i] - honey[0] # (2) bee_2 = accum_honey[n - 1] - accum_honey[i] # (3) honey_amount = max(honey_amount, bee_1 + bee_2) # (4) bee_1 = accum_ho.. 2024. 1. 21.
[Baekjoon-Python] 20056 : 마법사 상어와 파이어볼 https://www.acmicpc.net/problem/20056 접근 행, 열의 양 끝이 연결되어 있기 때문에 이동한 (r, c)는 N으로 나눈 나머지로 구한다. 이동 후 파이어볼이 2개 이상 있는 칸은 모든 파이어볼의 질량과 속력을 합한다. 합쳐진 파이어볼을 4개로 나누고 질량이 0이면 소멸한다. 풀이 from sys import stdin def move() -> dict: # (1) moved_grid = {} for (r, c), fire_balls in grid.items(): for m, s, d in fire_balls: nr = (r + direction[d][0] * s) % N nc = (c + direction[d][1] * s) % N if (nr, nc) in moved_gri.. 2024. 1. 21.
[Baekjoon-Python] 1092 : 배 https://www.acmicpc.net/problem/1092 접근 크레인과 박스를 내림차순 정렬한다. 첫 번째 크레인이 첫 번째 박스를 옮길 수 없으면 -1을 출력한다. 두 번째 크레인부터 순회하면서 박스를 옮길 수 있는지 확인한다. 박스를 옮길 수 있는 크레인 중에서 가장 적게 옮긴 크레인이 박스를 옮긴다. 박스를 옮길 수 있는 크레인이 없거나 가장 적게 옮긴 크레인이 첫 번째 크레인이면 첫 번째 크레인이 박스를 옮긴다. 풀이 from sys import stdin from collections import deque n = int(stdin.readline()) crane = sorted(list(map(int, stdin.readline().split())), reverse=True) # (1.. 2024. 1. 21.
[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.

티스토리툴바