kthng

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

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로 시간초과인지 테스트해보았지만 역시나 시간초과^^

boj 11060 : 점프점프 https://www.acmicpc.net/problem/11060 삼성 코드그라운드에서도 비슷한 문제를 본 기억이 있다. 해결방법은 간단하다. dist[i]를 i번째 돌까지의 최소 점프 횟수, a[i]는 i번째 위치의 점프력이라고 두면 1. dist[j] = min(dist[j],dist[i] + 1) { i+1

boj 2343 : 기타 레슨 https://www.acmicpc.net/problem/2343 얼핏 보면 간단하지만, 아이디어가 쉽게 떠오르지 않아 고생했던 문제이다.ㅜㅜ 1. f(a) : 블루레이 크기가 a일 때 M개 모두 녹화할 수 있는가? true or false2. f(a)가 true인 최소의 a값이 답이다. 이분탐색을 이용하면 시간안에 문제를 해결할 수 있다.f()의 시간복잡도는 n, 이분탐색의 시간복잡도는 logn이므로 총 시간복잡도는 nlogn이다.

boj 11501 : Stock(주식) https://www.acmicpc.net/problem/11501 언뜻 간단해보이지만 아이디어를 떠올리기가 쉽지만은 않은 문제이다. a[i]를 i번째 주식의 가격이라 할 때, i번째를 산다면 얼마에 팔 수 있는가?term_max를 팔게될 가격이라고 한다면, 1. term_max = max(a[k]) {k = i~n} 그렇다면 이득은 얼마인가? 2. i번째 얻는 이득 : term_max - a[i]; 위 알고리즘의 시간복잡도는 n이다.

boj 10453 : String Transformation (문자열 변환) https://www.acmicpc.net/problem/10453 A,B는 모두 좋은문자열이다.그러므로 A 에서 B로 바꾸는 과정은 모두 좋은문자열이다. 왜그럴까?A가 좋은 문자열이면 임의의 위치 i를 잡는다면 i전까진 b보다 a가 많고, i부터 끝까진 a보다 b가 많기 때문.따라서 A,B모두 좋은 문자열이라면 A에서 B로 최소이동으로 바꾸는 경로 또한 모두 좋은문자열이다.(정확한 증명은 안되었다..ㅜㅜ 직관적으로....) 그렇다면 이제, A를 B로 옮기기 위한 최소 이동횟수를 구해보자.예제의 aabbabab -> aaaabbbb 를 생각해보자.편의를 위해 b를 공백으로 생각하고, a만을 움직인다 생각해도 문제는 변함이 없다...