문제 링크 https://www.acmicpc.net/problem/25330 25330번: SHOW ME THE DUNGEON 올 여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임이다. 배경이 되는 나라는 $0, 1, 2, \cdots, N$번의 번호가 붙어있는 $N+1$개의 마을로 이루 www.acmicpc.net 문제 올 여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임이다. 배경이 되는 나라는 0, 1, 2, ⋯, N번의 번호가 붙어있는 N + 1개의 마을로 이루어져 있다. 0번 마을과 1, 2, ⋯, N번 마을을 오갈 수 있는 도로가 존재하고 ..

문제 링크 https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 문제 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주어진다. 1 x : 알파벳 x를 잊는다. 2 x : 알파벳 x를 기억해 낸다. 처음에 모든 알파벳을 기억하는 상태고, 모음은 완벽하게 외웠기 때문에 절대 잊지 않는다. 각 쿼리마다 완전히..

문제 링크 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이..

문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고,..

문제 링크 https://www.acmicpc.net/problem/28078 28078번: 중력 큐 처음에 왼쪽이 큐의 뒤, 오른쪽이 큐의 앞인 가로 방향의 빈 큐가 존재한다. 이 큐에서 공이나 가림막을 하나씩 큐의 뒤에 삽입하거나, 큐의 가장 앞에 있는 공이나 가림막을 꺼낼 수 있으며, 큐 www.acmicpc.net 문제 처음에 왼쪽이 큐의 뒤, 오른쪽이 큐의 앞인 가로 방향의 빈 큐가 존재한다. 이 큐에서 공이나 가림막을 하나씩 큐의 뒤에 삽입하거나, 큐의 가장 앞에 있는 공이나 가림막을 꺼낼 수 있으며, 큐를 시계방향이나 반시계방향으로 90도 회전시킬 수 있다. 큐 안의 가림막은 중력의 영향을 받지 않지만, 큐 안의 공은 중력의 영향을 받는다. 따라서 큐를 세로 방향으로 회전시켰을 때, 큐의 가..

문제 링크 https://www.acmicpc.net/problem/28125 28125번: 2023 아주머학교 프로그래딩 정시머힌 2023 APC를 총괄하고 있는 A.N.S.I 부회장 현빈이는 문제들을 검수하던 중 이상한 점을 발견하였다. 그것은 몇몇 단어들이 비슷하게 생겼지만, 다른 철자로 되어있었던 것이었다. 어리둥절한 현빈이 www.acmicpc.net 문제 2023 APC를 총괄하고 있는 A.N.S.I 부회장 현빈이는 문제들을 검수하던 중 이상한 점을 발견하였다. 그것은 몇몇 단어들이 비슷하게 생겼지만, 다른 철자로 되어있었던 것이었다. 어리둥절한 현빈이는 누가 이러한 짓을 저질렀는지 고민하던 와중, 어제 선우와 했던 대화가 문득 떠올랐다. 가뜩이나 A.N.S.I 부회장으로서 바쁜 현빈이는 철자..

문제 링크 https://www.acmicpc.net/problem/28136 28136번: 원, 탁! 최소 몇 번의 원, 탁!이 필요한지 출력한다. www.acmicpc.net 문제 현빈이는 수열을 좋아한다. 그중에서도 오름차순으로 정렬된 수열이라면 단연코 환장한다. 선우는 수열과 수학을 사랑하는 현빈이를 골탕 먹이고자 현빈이에게 숫자가 적힌 접시가 원형으로 놓여있는 원탁을 내밀었다. 각 접시에는 시계방향으로 1부터 N까지 번호가 붙어있고, i번 접시에는 ai가 적혀있다. N번 접시 다음에는 1번 접시가 등장함에 유의하자. 현빈이는 수열을 시계방향으로 읽고 있고, 원탁의 특성상 접시에 적혀있는 숫자를 시계방향으로 읽다 보면 숫자가 순환되기 때문에, 현빈이는 정렬된 상태를 볼 수 없다. 이에 현빈이는 ..

문제 링크 https://www.acmicpc.net/problem/28070 28070번: 유니의 편지 쓰기 유니가 편지를 써야 할 시기를 YYYY-MM 형식으로 출력한다. 편지를 써야 할 시기가 여러 개일 경우, 가장 앞선 시기를 출력한다. www.acmicpc.net 문제 남중 남고를 나온 유니는 주변에 군인인 친구들이 많다. 그런 유니는 군대에 있는 친구들에게 편지를 써 주려 한다. 하지만 편지를 써 줄 친구들이 많아 귀찮은 유니는 오직 한 달 동안만 편지를 쓰기로 한다. 한 달 동안만 편지를 쓰면 군대 안에서 편지를 받지 못하는 친구들도 있으므로, 가장 많은 친구가 군대에 있는 한 달을 찾으려 한다. 머리가 좋지 않아 그 한 달이 언제인지 모르는 유니를 위해 언제 편지를 써야 하는지 구해주자. ..

문제 링크 https://www.acmicpc.net/problem/3671 3671번: 산업 스파이의 편지 각 테스트 케이스에 대해 종이조각을 적절히 배치해서 만들 수 있는 서로 다른 소수의 개수를 출력한다. 이때, 모든 종이 조각을 사용하지 않아도 된다. (7과 1이 있을 때, 만들 수 있는 소수는 7, www.acmicpc.net 문제 안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요. 저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매우 유능한 산업 스파이이기 때문에, 연구 결과를 어렵지 않게 얻을 수 있었습니다. 하지만, 제가 올 것을 미리 알았는지 연구소에서는 연구 결과를 모두 서류 절단기에 넣어버렸습니다. 어쩔수 ..

문제 링크 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력 첫째 줄에 총 몇 개가 있는지 출력한다. 제한 1 ≤ A ≤ B ≤ 10^14 예제 입력 1 1 1000 예제 출력 ..

문제 링크 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net 문제 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다. 구구의 집으로 들어가는 입구는 한 개이며 입구과 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다. 구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는..

문제 링크 https://www.acmicpc.net/problem/25636 25636번: 소방차 ANA 도시는 $N$개의 교차로와, $M$개의 양방향 도로로 이루어져 있고, 교차로는 $1$번부터 $N$번까지 번호가 매겨져 있다. $S$번 교차로에는 ANA 도시의 유일한 소방서가 위치하는데, 무겸이는 이곳에 www.acmicpc.net 문제 ANA 도시는 N개의 교차로와, M개의 양방향 도로로 이루어져 있고, 교차로는 1번부터 N번까지 번호가 매겨져 있다. S번 교차로에는 ANA 도시의 유일한 소방서가 위치하는데, 무겸이는 이곳에서 소방차 운전 기사로 일하고 있다. 무겸이는 소방차를 타고 화재가 발생한 교차로에 출동해서 화재를 진압한다. 소방차에는 물을 담을 수 있는 물탱크가 있어서 이곳에 담은 물을 ..

문제 링크 https://www.acmicpc.net/problem/25195 25195번: Yes or yes 첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$) 이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는 www.acmicpc.net 문제 N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다. 투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다. 투어리스트 ..

문제 링크 https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 문제 정점이 N개인 트리가 있다. 정점에는 1부터 N까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다. 색은 섞이지 않고 색칠할 때마다 그 색으로 덮어진다. 단, 하얀색으로 색칠할 수는 없다. 아래 그림처럼 정점 10개로 구성된 트리가..

문제 링크 https://www.acmicpc.net/problem/23295 23295번: 스터디 시간 정하기 1 첫째 줄에는 스터디에 참가하고자하는 참가자 수 N과 스터디 시간 T가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 100,000) 다음 줄부터 참가하고자 하는 참가자들의 시간 정보가 N개 주어진다. 각 정보의 www.acmicpc.net 문제 의찬이는 여러 참가자들을 모아 알고리즘 대회 준비 스터디를 진행하고자 한다. 스터디에 많은 참가자들이 모였지만, 각자 가능한 시간들이 달라 의찬이는 스터디 시간을 정하는데 어려움을 겪고 있다. 의찬이는 바쁘면서도 한가하기 때문에 최대한 다른 참가자들의 시간에 맞춰서 스터디를 진행하고자 한다. T시간 동안 스터디를 진행하고자 할 때 참가자들..