문제 설명올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다.금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 많은 나라금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와..
문제 설명수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/13913 제한 사항 풀이문제를 요약하면, +1, -1, *2를 이용하여 N부터 K까지 도착하는 최소 이동 횟수와 경로를 출력하는 것이다.BFS 혹은..
문제 설명각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다.트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다.아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/11812 제한 사항 풀이문제를 요약하면, N개의 노드를 K진 트리로 만들어 Q개의 쿼리를 처리하면 된다.Q개의 쿼리는 주어지는 두 노드의 거리를 구하는..
문제 설명어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.https://www.acmicpc.net/problem/2042 제한 사항 풀이문제를 요약하면, 트리에 대한 정보가 주어지고, M개의 쿼리가 주어지면 해당하는 연산을 하는 것이다.쿼리의 종류로는 특정한 지점의 수를 변경하는 것과 주어진 구간의 곱을 출력하는 것이 있다. 해당 문제를 풀기 위해서는 구간 트리를 사용..
문제 설명N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 제한 사항 풀이문제를 요약하면, LCA를 찾는 문제이다.LCA란 최소 공통 조상을 의미한다.예시에 주어진 트리를 보자.주어진 트리는 위와 같이 생겼고, 6번과 11번의 LCA는 2번이다. LCA를 구하는 유명한 방법은 두 가지이다.두 노드의 레벨을 동일하게 맞춘 뒤, 한 칸씩 위로 올라가며 LCA 탐색오일러 투어를 통한 LCA 탐색 첫 번째 방법은 부모 노드와 깊이를 모두 기록해야 된다.조금 번거롭다고 생각하여 간..
문제 설명트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1167 제한 사항 풀이문제를 요약하면, 트리의 지름을 구하는 것이다.트리의 지름이란 트리에 있는 노드 간의 거리가 가장 먼 두 노드의 거리를 말한다.트리의 지름을 구하는 방법은 크게 두 가지이다.DFS를 이용하는 방법DP를 이용하는 방법DFS를 이용하는 방법은 간단하다.임의의 노드를 고른 뒤 DFS를 통해 가장 먼 노드를 찾아낸다.가장 먼 노드는 트리의 지름에 포함되는 노드이다.따라서, 그 노드에서 가장 먼 노드를 다시 구하면 그 거리가 트리의 지름이 된다. 이를 증명하는 것은 간단하다.트리의 지름..
문제 설명피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 제한 사항 풀이피보나치 수열을 구하는 문제는 간단하다.설명에 나온대로 i-1, i-2를 더하면 된다. 하지만, 해당 문제에서는 N이 굉장히 크다.즉, $O(N)$만에 답을 구해도 시간초과라는 것이다. 해당 문..
문제 설명0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.1 ≤ i 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오. 제한 사항 풀이문제를 요약하면, N의 각 자릿수를 K번 교환하여 만들 수 있는 최댓값을 구하는 문제이다. 처음에는 N의 각 자릿수를 정렬하여 최대한 비슷하게 만드는 방식으로 문제를 풀려했었다.k번의 교환을 통해 0번째부터 k번째 수를 확정해가면 된다 생각했다.하지만, 이 방법은 반만 정답이다.만약 k가 N의 자릿수보다 많다면 곤란해진다.따라서, 해당 방법이 아닌 다른 방법이 필요하다. k-1번째 교환에서 큰 수를 만들었다 하여도 k번째에 더 작아질 수 있다.반대..
문제 설명러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다.블록 '|'블록 '-'블록 '+'블록 '1'블록 '2'블록 '3'블록 '4'가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, 수평)으로 흘러야 한다.파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블록 하나를 지웠다. 지운 블록은 빈 칸이 되어있다.해커가 어떤..
문제 설명오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오. 제한 사항 ..
