본문 바로가기

👨‍💻📱✍️🎢314

BOJ 11952 - 좀비 문제 백준 온라인 저지 - 11952번 풀이 과정 문제에서 주어진 좀비로 점령된 도시들을 이용해서 위험한 지역을 찾고, 이를 통해 도시 방문 비용을 계산하고 다익스트라 알고리즘을 이용해 최단거리를 계산합니다. 이때 도시에게 점령당한 도시는 최단 거리 계산 시 고려하지 않도록 하는 것에 유의합니다. 좀비에게 점령당한 도시를 기준으로 S 이하의 거리를 가지는 위험한 도시를 판단하기 위해서는 BFS 를 이용했습니다. 코드 import sys from collections import deque import heapq N, M, K, S = list(map(int, sys.stdin.readline().split())) P, Q = list(map(int, sys.stdin.readline().split())).. 2021. 3. 8.
BOJ 20055 - 컨베이어 벨트 위의 로봇 문제 백준 온라인 저지 - 20055번 풀이 과정 문제에서 제시한 규칙대로 동작하는 컨베이어 벨트를 구현하면 되는 문제입니다. 2차원 배열을 이용해서 컨베이어 벨트를 나타냈지만 사실 그냥 1차원 배열을 이용해서 구현해도 될 것 같습니다. 문제에서 주어진 네 가지 단계를 각각의 함수로 구현해서 검사해주는 방식으로 구현했습니다. 코드 import sys from collections import deque N, K = list(map(int, sys.stdin.readline().split())) belts = list(map(int, sys.stdin.readline().split())) def init_conveyor(): conveyor = [[0] * N for _ in range(2)] convey.. 2021. 3. 8.
BOJ 20044 - Project Teams 문제 백준 온라인 저지 - 20044번 풀이 과정 두 명씩 팀원을 구성할 때, 팀원들의 코딩 능력의 합들 중 가장 작은 경우를 최대화하는 문제입니다. 두 명씩 묶기 때문에 능력치를 기준으로 오름차순으로 정렬한 다음 양 끝에 있는 학생들끼리 묶어주면 되는 그리디 문제입니다. 코드 import sys N = int(input()) stats = list(map(int, sys.stdin.readline().split())) def solution(): stats.sort() answer = sys.maxsize for i in range(N): s = stats[i] + stats[2 * N - i - 1] answer = min(answer, s) return answer print(solution()) 2021. 3. 8.
BOJ 1644 - 소수의 연속합 문제 백준 온라인 저지 - 1644번 풀이 과정 N 이 주어질 때 연속된 소수의 합으로 N 을 만족시킬 수 있는 경우의 수를 찾는 문제입니다. 특정 수들의 합이 N 이 되기 위해서는 해당 수들이 N 보다 작아야 함은 자명합니다. 따라서 N 보다 작거나 같은 수들 중 모든 소수를 에라토스테네스의 체 를 이용해 먼저 구해놓은 다음 연속된 구간을 찾으면 됩니다. N 의 최대 값이 크기 때문에 O(N^2) 으로 모든 합의 경우의 수를 따지면 시간 초과가 발생합니다. 코드 N = int(input()) def eratos(n): sieve = [1] * (n + 1) for i in range(2, int(n ** 0.5) + 1): if sieve[i]: for j in range(i * 2, n + 1, i).. 2021. 3. 8.
BOJ 18242 - 네모네모 시력검사 문제 백준 온라인 저지 - 18242번 풀이 과정 네모네모 안과의 시력 검사를 통과할 수 있는 기능을 구현하는 문제입니다. 격자에는 단 하나의 직사각형이 존재한다는 보장이 있기 때문에 우리가 활용할 수 있는 첫번째 정보는 왼쪽 상단 모서리의 위치입니다. 이후 오른쪽 상단 모서리와 왼쪽 하단 모서리의 위치를 구해서 직사각형의 너비와 높이를 구하고 이를 활용해 직사각형의 각 변을 검사하면 됩니다. 코드 import sys N, M = list(map(int, sys.stdin.readline().split())) board = [list(sys.stdin.readline().strip()) for _ in range(N)] def get_pivot(board): pivot = None for x in ran.. 2021. 3. 8.
BOJ 9184 - 신나는 함수 실행 문제 백준 온라인 저지 - 9184번 풀이 과정 메모이제이션 으로 재귀 호출을 최적화하는 문제입니다. 문제에서 제시된 함수 구현을 동적 계획법 으로 구현하면 됩니다. 코드 import sys memo = [[[-1] * 51 for _ in range(51)] for _ in range(51)] def func(a, b, c): if a 20: return func(20, 20, 20) if memo[a][b][c] != -1: return memo[a][b][c] if a < b < c: memo[a][b][c] = func(a, b, c - 1) + func(a, b - 1, c - 1) - func(a, b - 1, c) else: memo[a][b][c] = func(a - 1, b, c) + f.. 2021. 3. 8.

티스토리툴바