CEO

문제 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람�� www.acmicpc.net 문제 풀이 N명이 한 줄로 서서 기다리고 있을 때, 볼 수 있는 사람의 수를 구하는 문제이다. 두 사람 A와 B가 서로 보기 위해서는 A, B 사이에 둘 보다 키가 큰 사람이 없어야 한다. 문제를 풀기 위해서는 `stack`을 활용하여, 현재 `top`보다 큰 키가 입력된다면, 이후에 입력되는 값은 현재의 `top`을 볼 수 없으므로 `pop`을 하여야 한다. 이와 반대의 경우 라면 `stack`에 추가한다. 주의해야 할 것은 연..

문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net 문제 풀이 문자열이 주어질 때, 폭발 문자열과 일치하는 부분이 있다면 제거가 가능하다. 문자열과 폭발 문자열이 일치하는 모든 부분을 제거하고, 남은 문자열을 반환한다. 만약, 남은 문자열이 없다면 FRULA를 반환한다. 이 문제는 전형적인 `stack`문제로 `stack`에 문자열을 하나씩 추가하면서, 폭발 문자열과 비교하여 제거 가능한지 파악 후에 제거하면 된다. 코드 from sys import stdin def solve(): stac..

문제 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 문제 풀이 빙산의 높이가 주어질 때, 1년이 지날 때마다 바다에 인접한 수만큼 빙산이 녹아서 없어진다. 이때 빙산의 영역이 2개 이상이 되는 최소의 시간(년)을 찾는 문제이다. 문제를 풀기 위해서는 BFS를 통해 영역을 탐색함과 동시에, 각 빙하가 바다와 인접하고 있는 수를 카운트하여 해결할 수 있다. BFS를 통해, 빙하인 부분부터 탐색을 시작한다. 빙하 주위가 바다라면, 딕셔너리를 통해 해당 지점을 카운트한다. BFS 탐색 후에, 탐색 가능한 ..

문제 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치�� www.acmicpc.net 문제 풀이 NxN에 시험관에 바이러스들이 있을 때, 바이러스의 종류는 1부터 K까지 존재한다. 이때, 1번 바이러스부터 우선적으로 전염될 때, S초에 X, Y에 전염된 바이러스의 종류를 출력하는 문제이다. 초기에 전염되지 않은 곳은 0, 바이러스가 있는 곳은 1 ~ K 사이의 수로 표시된다. BFS를 통해 탐색하여 문제를 풀 수 있다. 최초에 주어진 시험관에서 바이러스의 종류를 찾고, 좌표를 기록한다. 1번 바이러스 부터 전..

문제 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경�� www.acmicpc.net 문제 풀이 블루레이에 N개의 레슨이 들어가는데, 블루레이를 녹화할 때는 레슨의 순서가 바뀌면 안 되고 M개의 블루레이에 플레이 타임이 모두 같도록 해서 만들어야 한다. 이때 가능한 블루레이의 크기 중 최소를 출력하는 문제이다. 이 문제는 전형적인 이분 탐색 문제이다. start, end를 `max(lesson)`, `sum(lesson)`로 설정한다. 하나의 레슨을 담고자 한다면 최소 lesson에서 가장 큰 값은 되어야 한다. 하나의 블루레이에 모든 레슨을 ..

문제 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 풀이 문제에 F, S, G, U, D `(건물의 높이, 시작층, 가고자 하는 층, 한 번에 올라가는 층, 한 번에 내려가는 층)`가 주어진다. 시작 층에서 엘리베이터를 이용해 가고자 하는 층에 도달하는 최소 경우를 반환하는 문제이다. 만약 도달할 수 없다면 계단을 이용하라는 메시지를 출력한다. BFS를 통해 시작층 부터 올라가는 경우, 내려가는 경우를 탐색한다. 올라가는 경우 F보다 작거나 같아야 하며, 내려가는 경우는 0 보다 커야 한다. 재방문을 막기 위해 현..

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 16195번: 1, 2, 3 더하기 9 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이하 이어야 한다. www.acmicpc.net 문제 풀이 앞서 다룬 1, 2, 3 더하기 7을 이해하고 있다면 쉽게 풀 수 있는 문제이다. 1, 2, 3 더하기 7에서는 N을 구할 때 M 만큼 사용 가능한 경우만 구하면 된다. 이 문제에서는 M이하의 모든 경우..

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 15993번: 1, 2, 3 더하기 8 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다. www.acmicpc.net 문제 풀이 앞의 문제들과는 다르게, 홀수인 경우와 짝수인 경우에 구할 수 있는 경우의 수를 나눠서 출력하여야 한다. 따라서 DP를 구성할 때, `DP[홀수/짝수][N]`과 같이 선언하여서 각 경우에 대해 점화식을 통해 찾아가면 ..