kthng

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를 출력한다. 각 쌍의 합을 소수로 만들 수 있는지 확인하는 작업은 이분매칭과 유사한 방법등..

Rectangles [SCPC 2016 - 2차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=30 문제는 저 점 (7, 3.5)를 찾는 것이다.R1은 R3을 포함하고, R3는 R4를 포함한다. 그리고 R1,R3,R4는 서로 겹치지 않는다. 점 (7, 3.5)는 겹치지 않고 서로 포함관계에 있는 3개의 Rectangle 안에 포함되고, 위와같은 조건을 만족하면서 더 많은 Rectangle 안에 포함되는 점을 찾을 수 없으므로 답은 3을 출력하면 된다. 그렇다면 답은 어떻게 구할 수 있을까?먼저 R1에 포함되는 최대 집함을 찾아보자.Ri의 집합의 크기를 Si라 두면,R1은 R2,R3,R4를 포함하므로 S1 = max(S2,S3,S4)..