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가 주어진다. 각 문자..

파스칼의 삼각형 이항계수 문제는 조합 공식으로도 풀 수 있으나 파스칼의 삼각형을 이용하면 더 쉽게 답을 얻어낼 수 있다! 삼각형을 그리는 규칙 숫자가 들어갈 칸을 첫 번째 줄에는 1개, 두 번째 줄에는 2개, 세 번째 줄에는 3개 이런 식으로 한 줄씩 내려가면 한 칸씩 늘어나게 정삼각형 모양으로 만든다. 첫 번째 줄과 두 번째 줄의 3칸에는 1을 쓴다. 세 번째 줄부터는 줄의 양쪽 끝 칸에는 1을 쓰고 나머지 칸에는 바로 윗줄에 위치한 칸 중 해당 칸과 인접해 있는 두 칸의 숫자를 더해서 그 값을 쓴다. 위와 아래는 같다. n개의 물체에서 r개를 고른다 하자. 먼제 n개중 1개를 고정, A라 한다. 그럼 구하고자 하는 경우의 수는 A가 포함되는 경우와 포함되지 않는 경우 2가지로 나눌 수 있다. A가 포..

수열 수 또는 다른 대상의 순서있는 나열 나열 순서를 생각해야 하며 중복이 허용된다. 그렇다면 문제의 조건을 보자 N개의 자연 수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이여야 한다. 비내림차순 == 오름차순? 비내림차순은 점점 증가하는 수열이다. 오름차순과 같아 보이겠지만 오름차순은 인접한 두 수가 같을 수도 있는지 여부를 명확하게 알려주지 않지만 비내림차순은 같을 수도 있음을 명확히 해준 것 이런 경우를 위해 명시해준 것이 아닐까... 한다. 1 1 1 1 > 비내림차순이지만 과연 오름차순일까 1 2 3 4 > 비내림차순이고 오름차순 구현 들어온 수열 정렬 맨 앞칸부터 채우기 다 채우면 출력 간단하지만 수열의 중복과 순서에 대한 조건이 있기 때문에 적절하게 처..