4Legs_Archives

문제 링크 : www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 모든 도시에 전기가 공급되어야 하며, 한 도시가 둘 이상의 발전소에서 전기를 공급받지 않아야 한다는 점에서 MST를 구하는 문제로 접근할 수 있다. 둘 이상의 발전소에서 전기를 공급받지 않아야 한다는 것은 곧 사이클 없이 모든 정점을 잇는 것과 같기 때문이다. 단, 일반적인 MST 문제와의 차이는 아래의 예제와 같이 모든 정점이 서로 연결되어 있지는 않다..

문제 링크 : www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 정답인 a, b에 대해 제시된 수열은 항상 X(i+1) = a * Xi + b를 만족한다. 즉, 이는 일반항이다. 우리는 제시된 수열의 길이에 따라 Case를 구분할 수 있다. ① 제시된 수열의 길이가 1일 때 우리는 a, b를 특정할 수 없다. 다음 수가 아예 없기 때문이다. 이 경우 정답은 A이다. ② 제시된 수열의 길이가 2일 때 두 가지 경우로 나뉜다. 제시된 수를 29, 38이라 해보자. 이 때, a = 1, b = 9로 두었을 경우 a, b는 식을 만족..

문제 링크 : www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 이전에 포스팅했던 BOJ 1176 섞기와 동일한 접근법을 가진다. 어떠한 수들로 순열을 만들었을 때, 그 수들의 순서와 관계없이 우리는 이어붙인 수의 나머지만 알 면 된다. X개의 수를 이어붙인 큰 수를 k로 나눈 나머지가 r이라면, 그 r에 새로운 수 하나를 붙인 다른 한 수에 대한 나머지가 곧 X + 1개의 수를 이어붙인 큰 수를 k로 나눈 나머지이기 때문이다. 즉 1, 3, 5번의 수를 (3, 1, 5)의 순서로 이어붙이거나 (5,..

문제 링크 : www.acmicpc.net/problem/17501 17501번: 수식 트리 수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다. 연산자 노드는 항상 두 개 www.acmicpc.net 예제 1을 수식 트리로 나타내면 아래와 같다. 노드 1 ~ 5의 피연산자 노드를 각각 미지수 X1 ~ X5로 두었을 때, 이 수식 트리의 최종 결과값은 (X1 + X3 + X5) - (X2 + X4)가 된다. 즉, 트리의 형태와 상관없이 각 리프 노드(피연산자 노드)까지 도달했을 때, 해당 피연산자가 최종 식에서 어떤 부호를 갖는지만 파악하면 문제를 쉽게 해결할 수 있다. 만약 최종 식에서..

문제 링크 : www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제에서 한 아이의 위치를 옮기는 것은 항상 맨 앞으로 보내거나, 맨 뒤로 보내는 것에 유의하자. 이렇게 위치를 옮기는 횟수를 최소화하려면, 최초 아이들의 순서에서 이미 번호 순으로 서 있는 아이들을 제외한 나머지를 옮기면 된다. 즉, 예제의 (3 7 5 2 6 1 4) 에서, 이미 3, 5, 6의 올바른 순서가 존재하므로 이들을 제외한 나머지 7, 2, 1, 4를 옮기면 1 ~ 7의 오름차순 순서를 만..

문제 링크 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 최장 증가 수열(LIS)에 대해 숙지하고 있다면 쉽게 해결할 수 있는 문제이다. 전체 수열의 크기가 1000으로 작기 때문에 O(N^2)의 시간복잡도를 갖는 DP를 사용할 수 있다. 수열의 한 수에 대해, 왼쪽 끝에서 그 수에서 끝나는 LIS와 오른쪽 끝에서 시작해 그 수에서 끝나는 LIS 길이의 합(-1)이 곧 바이토닉 수열의 길이가 된다. (이 때, 원래의 수는 그 바이토닉 부분 수열에서 가장 큰 값이 된다.) ..

문제 링크 : www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 간선들은 그 간선의 양 끝 노드에 불이 옮겨진 순간부터 타는 시간이 절반으로 줄어들게 된다. 쉽게 설명하자면 다음 그림과 같다. 정점 A에 불이 먼저 붙은 상황이다. 이 때, A와 B를 잇는 간선은 A쪽에서 먼저 타게 된다. B쪽에는 아직 불이 도착하지 않았기 때문이다. 이제 정점 B에도 불이 붙었다. 이제는 간선의 남은 길이가 양쪽에서 타..

문제 링크 : www.acmicpc.net/problem/8984 8984번: 막대기 첫 줄에는 막대기의 개수와 수평선 사이의 간격을 나타내는 두 개의 정수 N과 L이 주어진다. 여기서 N은 1 이상 100,000 이하이고, L은 1 이상 1,000,000 이하이다. 그 다음 N 개의 줄에는 각 줄마다 막대 www.acmicpc.net 위쪽 수평선의 한 점과 아래쪽 수평선의 서로 다른 10개의 점을 잇는 막대기가 있는 상황을 가정해 보자. 이들 중 가장 긴 막대기를 선택한다고 해서, 가장 긴 지그재그가 나올지는 알 수 없다. 따라서 이 문제는 그리디 알고리즘이 아닌 다이나믹 프로그래밍으로 접근해야 한다. 어떤 한 막대에서 지그재그가 끝난 상황을 생각해 보자. 이 때, 맨 마지막 막대를 기준으로 지그재그는..

문제 링크 : www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 문제를 자세히 읽지 않는다면 최소 스패닝 트리(MST) 문제로 혼동할 수 있다. 제시된 조건 중, "따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다." 라는 내용이 있기 때문에 이 문제는 최소 스패닝 트리로 해결할 수 없게 된다. 다음과 같은 반례를 들 수 있다. 그림에서 붉은 색으..

문제 링크 : www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 문제를 간단하게 생각해야 깔끔하게 점화식을 구할 수 있다. "dp[k] = k일째 되는 날의 짚신벌레 개체 수"로 두고 문제를 풀어보자. 우선, 예제인 a = 2인 상황에서 짚신벌레가 증식만 한다고 가정한다면 다음과 같다. 0일째 되는 날: (0) 1일째 되는 날: (1) 2일째 되는 날: (2, 0) 3일째 되는 날: (3, 1, 0) 4일 째 되는 날: (4, 2, 1, 0, 0) 5일 째 되는 날: (5, 3, 2, 1, 1..