문제 구름나라는 N개의 도시와 N - 1개의 도로로 이루어진 나라이다. 각 도시는 1번부터 N번까지 번호가 붙어있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있으며, 같은 두 도시 쌍을 잇는 도로는 존재하지 않는다. 최근 구름나라의 도시들에는 불법 쓰레기 투기로 인한 환경적 문제가 발생하고 있다. 때문에 현재 i 번 도시에는 Ai만큼의 쓰레기가 쌓여 있는 상태이다. 구름나라의 청소부인 구름이는 구름나라를 돌아다니면서 쓰레기들을 치우려고 한다. 구름이는 최대 K만큼의 쓰레기를 담을 수 있는 커다란 쓰레기 봉투를 가지고 있다. 구름이는 현재 1번 도시에 있고, 다음 두 가지 행동들을 자유롭게 반복하여 청소를 하고자 한다. 구름이가 현재 머물고 있는 도시를 a번 도시라고 하자. a번 도시에 인접한..

문제 구름이는 N개의 직선 막대기를 가지고 있다. 구름이는 이 막대기들 중 일부를 잘 배치해서, 직사각형을 만들고자 한다. 직사각형을 만들기 위해서는 길이가 같은 막대기 두 쌍이 필요하다. 같은 쌍에 속한 막대기들을 마주 보게 배치하고, 다른 쌍에 속한 막대기들을 수직으로 배치하면 아래 그림과 같이 직사각형을 만들 수 있다. 길이가 a인 막대기와 길이가 b인 막대기 쌍을 사용해서 직사각형을 만들었을 때, 만들어진 직사각형의 넓이는 ab이다. 하나의 막대기는 하나의 직사각형을 만드는 데만 이용할 수 있고, 구름이는 가능한 많은 직사각형을 만들면서도 직사각형들의 넓이 합이 최대가 되기를 원한다. 구름이가 가지고 있는 막대기의 정보가 주어졌을 때, 구름이가 만들 수 있는 직사각형들의 넓이 합의 최댓값을 구하시..

문제 구름나라의 저편에 있는 무릉도원에는 높은 산봉우리들이 있는 산맥이 있다. 모든 산봉우리에는 동쪽을 바라보며 명상을 하는 신선이 한 명씩 있다. 그러던 중 신선들은 다른 신선들이 자신의 뒤통수를 바라봐서 그런지 뒤통수가 따가워짐을 느끼다가, 문득 얼마나 많은 신선이 자신의 뒤통수를 볼 수 있는지 궁금해졌다. 산맥의 모든 봉우리들은 왼쪽에서 오른쪽으로 정확히 일렬로 놓여있다. 왼쪽에서 a번째 봉우리에 있는 신선이 b번째 봉우리에 있는 신선의 뒤통수를 보기 위해선, a < b이면서 두 봉우리 사이에 있는 모든 봉우리의 높이가 a번째 봉우리의 높이보다 작아야 한다. 중간에 높은 봉우리가 있으면 그 뒤쪽 봉우리는 가려져서 보이지 않기 때문이다. 신선들의 궁금증을 해결해주기 위해, 산맥에 있는 봉우리의 개수와..

문제 구름 나라는 기존의 숫자 대신에 알파벳 소문자를 사용하여 숫자를 표기하기로 한다. 이를 구름 숫자라고 부른다. 구름 숫자는 아래의 표를 참고하여 작성할 수 있다. 구름 숫자는 효율성을 위해서 특별한 규칙을 가지고 있다. 여러 개의 구름 숫자를 이어서 작성하다가, 중복되는 알파벳이 있으면 합친다. 구름 숫자로 작성한 문자열이 주어질 때, 이를 기존의 숫자로 바꿔서 출력하는 프로그램을 작성하고자 한다. 이때 여러가지 경우의 수가 나온다면, 그 중 길이가 최대인 수를 출력하시오. 입력 첫째 줄에서는 문자열의 길이가 N(1 n >> input; for (int i = 0; i < n - 1; i++) { string word = input.substr(i, 2); if (matching.find(word)..

문제 구름이는 이상한 미로에 갇혔다. 미로는 N개의 방과 M개의 복도로 이루어져 있고, 각 방에는 1부터 N까지의 번호가 붙어 있다. 그리고 각 방의 바닥에는 1부터 10사이의 정수 Ai가 쓰여있다. 이 이상한 미로에는 이상한 규칙들이 있다. 방에서 움직이는 데 걸리는 시간은 고려하지 않는다. 미로에 있는 모든 복도는 양방향으로 이동할 수 있고, 복도마다 지나가는 데 걸리는 시간이 정해져 있다. i번 방과 j번 방이 복도로 직접 연결되어 있고, j번 방과 k번 방이 복도로 직접 연결되어 있을 때, 두 복도를 이용해 i번 방에서 k번 방으로 이동하려면 i를 Ai로 나눈 나머지와 k를 Aj로 나눈 나머지가 같아야 한다. 구름이는 현재 1번 방에 있고, 탈출구는 N번 방에 있다. 구름이가 이 이상한 미로에서 ..

문제 구름이가 사는 구름 나라는 N개의 섬으로 이루어져 있다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 구름 나라는 사람들이 섬과 섬 사이를 편하게 이동할 수 있도록 다리를 M개 설치했다. 설치된 다리들은 아래의 특징들을 만족한다. 모든 다리는 단방향으로만 이동 가능하다. 다리가 잇는 두 섬은 항상 다른 섬이다. 구름이는 현재 K번 섬에 있고, 다른 섬들을 둘러본 뒤 다시 K번 섬으로 돌아오려고 한다. 그렇지만 오래 돌아다니는 것은 피곤한 일이기 때문에, 구름이는 최소한의 섬만 거치는 경로를 택할 것이다. 구름이를 도와 최소 몇 개의 섬을 거쳐서 원래 구름이가 있던 섬으로 돌아올 수 있을지 알아보자. 단, 구름이는 K번 섬 이외에 최소 하나 이상의 다른 섬을 방문해야 한다. 입력 첫째 줄에 섬의 개..

문제 "발 없는 말이 천 리 간다"는 옛말이 있듯, 한 번 퍼져나가기 시작한 소문은 막을 수 없이 퍼져나간다. 구름이는 N명의 친구가 있고, 그 친구들 중에는 M쌍의 친구 관계가 있다. 구름이가 만약 어떤 친구에게 소문을 퍼뜨리게 된다면, 그 소문은 친구의 친구, 친구의 친구의 친구... 를 타고 퍼져나갈 것이다. 구름이가 1번 친구에게 소문을 퍼뜨렸을 때, 그 소문을 듣게 될 친구가 몇 명이나 될지를 구해보자. 입력 첫 번째 줄에는 구름이의 친구의 수 N(1 u >> v; edge[u].push_back(v); edge[v].push_back(u); } dfs(1); cout

문제 구름이는 구름 사이트의 UXUI디자이너로 일하게 되었다. 구름이의 첫 업무는 구름 사이트에서 사용자들이 자주 실행하는 이벤트를 정리하는 일이다. 이때 이벤트란 사용자가 웹사이트에서 실행하거나, 클릭한 것을 의미한다. 구름이는 이를 위해서 사용자들이 취할 수 있는 이벤트를 N개로 규정하고, 각각의 이벤트에 1번부터 N 번까지 번호를 붙였다. 구름이는 이어서 M명의 사용자가 구름 사이트에서 이벤트를 실행한 내역을 추출하였다. 추출한 정보를 바탕으로 구름이는 사용자들이 가장 자주 실행하는 이벤트들을 알아내고자 한다. 한 사람이 같은 이벤트를 여러 번 실행한 경우에도 중복으로 세어준다. 구름이를 도와 M명의 사용자들이 가장 자주 실행했던 이벤트들을 찾아 출력하시오. 입력 첫째 줄에 구름이가 정리한 이벤트의..

문제 바닷가에 놀러 간 구름이는 모래사장에서 모래 섬을 만들었다. 구르미는 자신이 만든 모래 섬에 다리를 세우고 싶어한다. 다리를 그냥 만들 수 있지만, 다리는 섬과 섬을 이어줄 때 그 의미가 있다고 생각을 했다. 구르미는 섬을 만들기 위해서 모래사장에 물을 붇기로 한다. 모래 섬은 주변에 물이 있으면 무너져 내린다. 현재 모래사장은 세로의 길이가 n, 가로의 길이가 m 크기이다. 모래사장을 1*1크기로 나누었을 때, 가장 왼쪽 위부터 i번째 줄의 j번째 칸을 arr[i][j]라고 표현할 수 있다. arr[i][j]의 값이 0이라면 이미 물에 가라앉았다는 의미이다. arr[i][j]이 양의 정수라면, 현재 위치의 모래의 고도이다. 모래는 주변의 물의 양에 따라서 매분마다 무너져 내린다. arr[i][j]..