ㅁㅁ

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

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)..

codeground : 프리랜서 [SCPC 2016 - 2차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=31 간단한 DP로 해결할 수 있다.일하는 데 일주일이 걸리는 P사의 각 주당 금액 을 Pi, 이주일이 걸리는 Q사의 각 주당 금액을 Qi라 하고, i번째 주에 받을 수 있는 가장 큰 금액을 Ai라 한다면, Ai = max(Ai-1+ Pi, Ai-2 + Qi) 위와같은 단 하나의 점화식으로 DP를 구성하면 가뿐하게 AC를 받을 수 있다.

codeground : 대피소 [SCPC 2016 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=28 떠올릴 수 있는 가장 간단한 방법은 v번의 다익스트라를 하는 것. 하지만 이 방법은 간단히 시간초과임을 알 수 있다. 그렇다면 다른 해결방법이 있을까? 이 문제는 단 한번의 다익스트라로 해결이 가능하다.heap에 모든 대피소를 넣고 시작하면 된다. 또한, 경로의 길이가 같을 경우 대피소번호가 작은 대피소를 선택하는 것도 동시에 해결해주면 된다. 알고리즘을 간략히 써보면, 1. 새로운 경로가 더 작으면 힙에 push. dist 갱신 위에께 일반적인 다익스트라 알고리즘이라면, 이문제에 해당하는 알고리즘은 다음과 같다. 1. 새..

codeground : 캠퍼스와 도로(1) [SCPC 2015 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=15 SW역량테스트를 맞아 codeground문제들도 써보려고 한다.그 첫번째 문제..이 문제는 v번의 다익스트라 알고리즘으로 떠오르는 아이디어 그대로 해결할 수있다.시간복잡도는 v*(v+e)log(v+e)가 되어 시간안에 충분히 해결할 수 있을 듯 하다.다만, 방문하는 도시까지의 거리가 같을 때가 문제 ㅜㅜ...힙에 push하기 전에 방문노드를 체크해주면 왜안되는지 모르겠다. 아직 밝혀내지 못했음... 해결한 방법은, 코드가 조금 길어지긴하지만 스타팅 지점인 v번째 도시에 대해 다익스트라 알고리즘으로 모든 경로까지..