kthng

https://www.acmicpc.net/problem/1647 최소 비용의 간선으로 두 마을을 나누는 문제이다.MST(Minimum Spanning Tree)를 약간만 응용하면 가능한 문제이다. MST를 푸는 두 알고리즘 중, 크루스칼 알고리즘으로 MST문제를 해결하다가 말면 성공적으로 도시를 분할할 수 있다.집의 개수가 N개라면 가장 적은 비용의 N-1개의 간선만 연결한다면 모든 집을 최소 비용으로 연결할 수 있다.여기서, 1개만큼 간선을 덜 연결하면, 즉 N-2개만큼의 간선을 연결하면 2그룹의 마을로 나누어지면서 문제가 해결된다. 문제에서는 언급하지 않았지만, 좀더 나아가 3그룹, 4그룹의 마을로 나누기 위해서는 어떻게하면 좋을까?더보기마찬가지로 N-3, N-4개의 간선만 연결하면 3그룹, 4그룹..

boj 1799 : 비숍https://www.acmicpc.net/problem/1799  기본적인 DFS + 커팅 방법을 사용하여 해결할 수 있다.백준 9663번 N-Queen와 유사하다. 0. DFS + 커팅방법지정한 y, x에 놓을 수 있는지 판단하기 위해 (y-1,x-1), (y-2,x-2) ... 를 모두 확인하면 판단을 위해 O(N)의 복잡도가 추가로 소모된다. 판단은 O(1)로 끝내야 한다. true나 false를 담은 check배열을 이용하여 한 번의 접근으로 말을 놓을 수 있는지 판단하도록 모델링해야 한다. 이후, DFS + 커팅 방법을 보완하기 위해 크게 2가지 기법을 추가로 사용하였다.1. 좌표변환위와 같이 좌표 변환을 끝내 놓으면, N-Queens문제보다 더 쉬운 N-Rooks 문제..

https://www.acmicpc.net/problem/16153 16153번: 비트와 가희 첫째 줄에 N(0 ≤ N

https://www.acmicpc.net/problem/11001 11001번: 김치 첫 번째 줄에 날짜의 수와 시간 제한 N, D가 주어진다. (1 ≤ D ≤ N ≤ 100,000) 두 번째 줄에 온도 Ti가 주어진다. N-1 이하의 정수 i에 대해서 Ti >= Ti+1을 만족하며, 109 이하의 자연수이다. 세 번째 줄에 www.acmicpc.net (숙성 시간) * (김치를 꺼낼 때의 온도) + (김치를 넣은 날 가치) 의 최대값을 출력해주는 문제이다. Divide And Conquer 최적화 기법을 사용하여 해결할 수 있다. Divide And Conquer 최적화 기법을 적용하기 전, 전제 하나를 증명하고 시작하자. [전제 증명] *전제1* i0 < i1, j0 < j1일 때, i0번째 날에 ..

https://www.acmicpc.net/problem/20193 20193번: 화려한 정사각형 평면에 N개의 점 P1(x1, y1), P2(x2, y2), . . . , PN(xN, yN)이 주어지며, 각각의 점들은 총 K개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 {1, 2, . . . , K} 중의 한 정수로 표현된다. 어떤 정사각형이 각 K www.acmicpc.net 2

https://www.acmicpc.net/problem/1214 1214번: 쿨한 물건 구매 첫째 줄에 D, P, Q가 주어진다. 모두 109보다 작거나 같은 자연수이다. www.acmicpc.net D, P, Q가 각각 $10^9$이하의 자연수일 때, D

https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net DP 냄새가 강하게 나는 문제이다. 낮은 탑 높이의 최대값을 f(idx, diff)로 두면. 아래와 같이 점화식을 세울 수 있다. 1. f(-1, 0) = 0 2. f(idx, diff) = max( [1], [2], [3]) 2-1. [1] : f(idx - 1, diff) 2-2. [2] : f(idx - 1, diff + a[idx]) + a[idx] 2-3. [3] : f(..

https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 풀이중.... 대략 이런느낌이다. 예제의 {1, 4, 7, 10, 11, 12} 에서 {1, x} 에서 x를 1과 짝지었을 때 소수가 되는 수라고 할 때, {1, 4, 7, 10, 11, 12} - {1, x} 에서 각 쌍의 합을 소수로 만들 수 있는 모든 x를 출력한다. 각 쌍의 합을 소수로 만들 수 있는지 확인하는 작업은 이분매칭과 유사한 방법등..

boj 2381 : 최대거리 https://www.acmicpc.net/problem/2381 n^2만에 해결할 수 있는 방법은 간단히 떠올릴 수 있다. 하지만 n이 최대 50000이기 때문에 시간초과. nlongn 이하의 해결법을 찾아야한다. 답은 (x+y의 최대값) - (x+y의 최소값), (x-y의 최대값) - (x-y의 최소값) 둘 중 큰값이 답이다.응??? 증명을 해보자.1. (x+y의 최대값) - (x+y의 최소값)이 답일 경우1.1 앞 괄호를 (x1,y1), 뒷 괄호를 (x2,y2)라 두면,1.2 x1 > x2이고, y1 > y2의 경우만 가능하다.1.3 그렇다면 만약 x1 < x2이거나 y1 < y2라면? 답에 모순이 생기지 않을까?x1 < x2이거나 y1 < y2라도 상관없다는것을 증명해..

boj 1238 : 파티 https://www.acmicpc.net/problem/1238 시간초과가 나지 않겠나? 라는 의문을 가졌지만, 잘 생각해본다면 단 두번의 다익스트라로 해결이 가능하다.^^.. 우선 파티장소에서 모든마을까지는 단순한 다익스트라의 구현으로 구할 수 있다.그렇다면 각각의 마을에서 파티장소까지의 경로는 어떻게 구할 수 있을까?답은 경로를 거꾸로 저장한 edge를 저장하는 것으로 해결 가능하다.a->z 경로의 최단거리는 반대경로의 최단거리와 같다. 호기심에 floyd로 시간초과인지 테스트해보았지만 역시나 시간초과^^