백준

문제 링크 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/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을 먼저 빼낼 경우 최대 봉투수를 보장하기 위해 고려할 것들이..

문제 링크 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제 풀이 이중 for문으로 하나하나 일치 여부를 확인하기에는 전화번호 개수 범위가 최대 10000개까지로 시간 초과 가능성이 높았습니다. 그래서 비교 횟수를 최소화하는 방법을 고민하던 중, 문자열의 정렬 원리를 통해 해결했습니다. 문자열은 대소비교를 통해 정렬되는 숫자와 달리 앞에서부터 비교되어 정렬됩니다. 예를 들어 아래 숫자를 311 27625999 3112..