문제 링크 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 풀이 from collections import deque def bfs(): q = deque() q.append([0, 0, k]) visited[0][0][k] = 1 while q: x, y, z = q.popleft() if x == n - 1 and y == m - 1: return visited[x][y][z] for dir in r..
파이썬
문제 링크 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 앞서 포스팅한 옥상정원 꾸미기와 유사한 방법으로 해결할 수 있었습니다. n = int(input()) nums = list(map(int, input().split())) stack = [] result = [] for i in range(n - 1, -1, -1): num = nums[i] while stack and stack[-1]
문제 링크 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 문제 풀이 단순히 빌딩 하나씩을 확인하며 더 낮고 오른쪽에 있는 빌딩들을 찾을 수도 있지만 시간 초과의 문제가 발생합니다. 문제의 해결 방안은 반대로 현재 기준의 빌딩이 보여질 수 있는 왼쪽의 높은 빌딩들을 찾아나가는 것입니다. for b in buildings: while stack and stack[-1]
문제 링크 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 문제 풀이 총 2가지를 구해야하는데, 주어진 양의 정수 k개만큼 특정 문자를 포함하는 가장 짧은 문자열의 길이와 가장 긴 문자열의 길이를 구해야 합니다. 최소 길이가 되려면 어차피 문자열의 첫 번째와 마지막 글자가 k개에 포함되는 특정 문자여야 합니다. 결국 처음과 마지막 글자가 특정 같은 문자인 문자열을 구하되 최소길이와 최대길이를 구하면 되는 것입니다. 문제를 해결하기 위해 de..
문제 링크 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 전형적인 BFS 문제로 문제 조건을 잘 따라가다보면 해결할 수 있는 문제입니다. from collections import deque m, n = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] visited = [[0] * m for _ in range(..
문제 링크 https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 문제 풀이 def check(input_str): stack = [] flag = False for str in input_str: # if str == 'A' and (len(stack) = 4 and stack[-4:] == ['P', 'P', 'A', 'P']: for _ in range(..
문제 링크 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 풀이 import heapq n = int(input()) times = [] for _ in range(n): times.append(list(map(int, input().split()))) times.sort() room = [] heapq.heappush(room, times[0][1]) for i in range(1, n): if times[i][0] < room[0]: heapq.heappush(room, times[..
문제 링크 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 풀이 n = int(input()) result = 0 while n % 5 != 0 and n >= 3: n -= 3 result += 1 if n % 5 == 0: result += n // 5 else: result = -1 print(result) 5kg 봉지를 최대한 많이 사용하는 것이 핵심인 문제였습니다. 처음부터 5kg을 먼저 빼낼 경우 최대 봉투수를 보장하기 위해 고려할 것들이..
