https://www.acmicpc.net/problem/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 먼저 이 문제의 조건을 읽어봅시다. 1. 교차로의 개수(= 노드의 개수) 및 시작점과 끝점이 주어지고 기다릴 시간이 주어집니다. 2. 그리고 인접행렬이 주어지는데, 0이면 길이 없는 것이고, 1 이상이면 해당 값만큼의 시간을 들여 노드 간을 이동할 수 있습니다. 3. 문제에서는 시작점에서 시작해서 끝점에서 끝나는 경로들 중에서 이동하는데 총 걸리는 시간이 기다릴 시간만..

https://www.acmicpc.net/problem/22343 22343번: 괄호의 값 비교 첫 번째 테스트 케이스: f[A] = f[((()))] = 4이고, f[B] = f[()(())] = 3이므로, f[A] > f[B]이다. 두 번째 테스트 케이스: f[A] = f[(((())))] = 8이고, f[B] = f[()()()()()] = 5이므로, f[A] > f[B] 이다. www.acmicpc.net 문제를 해석해보면 아래와 같습니다. 1. 함수 F가 있는데, F[()] = 1입니다. 2. F[()] = F[] * 2이고, F[] = F[] +F[] 이런식으로 동등한 위치에서의 괄호들의 F 값들은 더하고, 씌워져 있는 만큼 2를 곱해줍니다. 3. 괄호들이 제대로 씌워진 문자열 a,b가 주어..

https://www.acmicpc.net/problem/1578 1578번: 세계 정복 첫째 줄에 국가의 수 N과 K가 주어진다. N은 K보다 크거나 같고, 50보다 작거나 같은 자연수이고, K는 20보다 작거나 같은 자연수이다. 둘째 줄에는 각 나라에 살고 있는 사람의 수가 공백으로 구분 www.acmicpc.net 문제의 조건을 요약하자면 아래와 같습니다. N개의 국가가 있으며 각 나라마다 인구 수가 주어집니다. 그룹이란 K명으로 이루어지며, 그룹 내의 사람들의 국적은 전부 달라야 합니다. 문제에서는 그룹을 최대 몇 개로 나눌 수 있는지를 물어봅니다. 일단 관찰을 해봅시다. 그룹을 G개로 쪼갤 수가 있다면, 맨 마지막 그룹을 버림으로써 G-1개로도 쪼갤 수 있는 걸 알 수 있습니다. 그렇다면, 특정..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제를 읽어보면 조건들은 아래와 같습니다. 땅과 바다로 구분된 지도가 주어집니다. 상하좌우로 인접한 땅은 하나의 섬으로 봅니다. 목표는 섬을 모두 잇는 겁니다. 두 섬은 바다에 다리를 건설해서 이을 수가 있습니다. 다리는 바다에만 놓을 수 있습니다. 그리고 다리의 길이는 다리가 격자에서 차지하는 수로, 2 이상이 되어야 합니다. 또한, 다리는 중간에 방향이 바뀌면 안됩니다. ..

https://www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net 문제의 조건들을 파악해봅시다. 1. 색상들의 이름들과, 닉네임들이 C, N개씩 주어짐 2. 이후에 Q개의 팀 이름들이 주어질 때, 각 이름들이 이 나온다음에 이 나오는 구조로 이루어져 있는가를 출력 조건만 보면 일단 단순합니다. 문제 길이도 그렇게 길지는 않죠. 다만, 색상의 종류와 닉네임의 개수가 C, N개인데 모든 조합을 파악하기에는 4000 * 4000 개이며, concaten..

https://www.acmicpc.net/problem/14727 14727번: 퍼즐 자르기 히스토그램을 구성하는 직사각형의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 이어 N개의 줄에 걸쳐 각 직사각형의 높이인 정수 Hi(1 ≤ Hi ≤ 1,000,000)가 주어진다. www.acmicpc.net 문제를 읽고 조건들을 파악해보면 아래와 같습니다. 1. 히스토그램의 넓이가 1씩 쪼개어졌을 때의 높이가 주어짐 2. 히스토그램의 내에서 그릴 수 있는 제일 넓은 직사각형의 넓이를 출력 저는 예전에 히스토그램에서 큰 직사각형 찾는 문제들을 푼 경험이 있어서 이 문제의 조건들을 보자마자 Monotone Stack으로 풀 수 있다는 걸 알아차렸습니다. (물론, 분할 정복을 활용하거나, Segment Tr..