본문 바로가기

PS109

[Baekjoon-Python] 17143 : 낚시왕 https://www.acmicpc.net/problem/17143 접근 격자의 열 크기(C)가 5라면 상어가 이동할 때 인덱스(c)는 0, 1, 2, 3, 4, 3, 2, 1, ...이 된다. 상어가 움직일 때 인덱스에 사이클이 발생한다. 사이클 길이는 2 * (C - 1)이다. 상어의 이동 후 인덱스를 중복없이 한 번에 찾도록 최적화해야 시간 초과가 발생하지 않는다. 열, 오른쪽 방향 기준으로 상어의 이동 후 인덱스는 (현재 인덱스 + 속력) % 열 사이클 길이 즉, (c + s) % (2 * (C - 1))이다. 풀이 from sys import stdin def catch(j): for i in range(R): # (1) if (i, j) in sharks: return sharks.pop((i.. 2024. 1. 23.
[Baekjoon-Python] 9251 : LCS https://www.acmicpc.net/problem/9251 접근 첫 번째 문자열의 알파벳을 두 번째 문자열과 비교하면서 공통 부분 수열 길이를 메모이제이션한다. 풀이 from sys import stdin letter_1 = stdin.readline().rstrip() letter_2 = stdin.readline().rstrip() dp = [0] * len(letter_2) for let_1 in letter_1: cnt = 0 # (1) for i, let_2 in enumerate(letter_2): if dp[i] > cnt: # (2) cnt = dp[i] elif let_1 == let_2: # (3) dp[i] = cnt + 1 print(max(dp)) (1) cnt는 전 인덱스.. 2024. 1. 22.
[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.

티스토리툴바