Python

문제 링크 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 풀이 from collections import deque def bfs(): q = deque() q.append([0, 0, k]) visited[0][0][k] = 0 while q: x, y, z = q.popleft() if x == h - 1 and y == w - 1: return visited[x][y][z] if z > 0: for hdir in r..

문제 링크 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[..