목록백준 (3)
minkylee
문제크기가 N X N 인 도시가 있고 집과 치킨집이 주어진다. M개의 치킨집을 남기고 모두 폐업시키려고 할 때 도시의 치킨 거리의 최소값을 구해라치킨거리 : 집과 가장 가까운 치킨집 사이의 거리, 각각의 집은 치킨 거리를 가지고 있다.도시의 치킨 거리 : 모든 집의 치킨 거리의 합이다.예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.0 2 0 1 01 0 1 0 00 0 0 0 00 0 0 1 10 0 0 1 20은 빈 칸, 1은 집, 2는 치킨집이다.(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.(5, 4)에 있는 집과 ..
문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다LCS LCS는 DP 알고리즘의 대표적인 문제이다.사실 브루트포스로도 풀 수 있는데 부분 문자열을 모두 구하고 비교해야 하므로 시간복잡도가 $2^n$ 인 무시무시한 숫자가 나온다. 두 개의 문자열을 A, B라고 하자,현재 보고있는 문자가 A[i] 와 B[j] 일 때, A[i]와 B[j] 가 같을 경우 최장 공통 부분 수열은 A[i - 1] B[j - 1]까지의 최장공통 부분 수열에 현재 문자를 더한 것과 같다. ABC 와 BC라는 실제 문자열을 가지고 생각해보자 현재..
문제 알파벳 소문자로 구성된 길이 1 이상의 두 문자열 X, Y가 있다. 이 문자열들의 임의의 위치에 공백을 삽입하여 두 문자열의 길이를 같게 만든 다음, 앞에서부터 한 글자씩 살펴보면서, 같은 위치에 있는 두 문자 X[i], Y[i]에 대해서 다음과 같이 점수를 계산한다. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다. 입력 첫째 줄에 세 정수 A, B, C (0 < A ≤ 10,000, -10,000 ≤ B, C < 0) 가 주어진다. 그리고 둘째 줄에 X가, 셋째 줄에 Y가 주어진다. 각 문자..