https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 부분합 + 그리디 문제. 꿀벌 둘을 A,B ( B가 더 오른쪽에 있는 꿀벌 ) 벌통을 C로 두면 크게 세가지 경우의 수가 있을 수 있다. 1. A < B < C 순 배치. 이 경우에 있어서, 꿀통인 C는 오른쪽 끝에 위치하는것이 가장 이득이 되고, 첫번째 꿀벌 A는 가장 왼쪽 끝에 위치하는것이 가장 이득이 된다. 남은 꿀벌 B가 어디에 있느냐에 따라서, (전체 꿀 + B~C 이동에서의 꿀 - A, B지점에서의 꿀) 을 계산해주면 된다. 벌이 있는 곳에서는 꿀을 딸 수 없기 때문에 A, B 지점의 꿀은 계산에서 따로 빼줘야 함에 유의할것...

https://www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net 편집거리를 계산해내는 문제. PHP levenstein() 함수를 써먹고싶어지는 문제다 "편집 거리" 로 표현해 두었지만, 실제로 정확한 용어는 levenshtein distance 이다. 처음 발견한 사람이 레벤슈타인 이었나 보다. 위키피디아에서의 레벤슈타인 거리의 정의는 아래와 같다. 해당 점화식을 해석해서 DP로 기술할수 있는 분들은 건너뛰셔도 된다. 레벤슈타인 거리는 보통 O(N^2) DP로 해결하게 되는데, 두 문자열을 A, B라고 할때 DP[i][j]..

https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 소인수분해를 빠르게 해주면 되는 문제. "런타임 전의 전처리" 태그를 붙여줘도 나쁘지 않지 싶다. 소인수분해를 $k_i$를 입력받을때마다 직접 해주면 시간초과를 받기 쉽다. 소인수 분해를 위한 할수 있는 모든 준비를 미리 처리해둬서 최대한 빠르게 소인수분해를 해야 한다. 이를 위해서 수 k의 1이 아닌 약수 중 가장 작은 수를 미리 배열에다가 전처리해서 저장해줬다. 이렇게 하면 $k_i$를 입력받았을때..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net BFS 응용 pair 로 좌표를 관리해줘도 되는데, 나는 그냥 편의상 x*1000+y 로 묶어서 1차원 배열로 만들어서 BFS를 돌려주었다. 불을 켜는 경우와 실제로 탐색하는 경우를 분리해줘야 하는데, 이를 위해서 방문체크를 위한 vis배열과 불이 켜져있는지 체크를 위한 light 배열 두개를 만들어서 각각 관리해줬다. 프로그램 작성 과정에서도..

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 말이 세 수의 합이지 브루트포싱하면 O(N^4)이다... 세 수의 합 d와 배열 안의 어떤 수 U가 같아지는 경우를 찾아야 한다. 브루트포스로 접근했을 때 세 수가 O(N^3), U와 매칭시키면서 O(N)이므로 전체 시간복잡도가 O(N^4)가 되어서 시간초과를 받는다. 밋인더미들 알고리즘을 사용해서 선택해야하는 네 수 (세 수 a,b,c 와 U) 를..

https://www.acmicpc.net/problem/1174 1174번: 줄어드는 수 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 www.acmicpc.net 브루트포스 문제. 줄어 드는 수 중 가장 큰 수는 9876543210 이므로, 0부터 숫자를 1씩 증가하면서 "줄어드는 수" 인지 체크하는 방법은 TLE를 받게 된다. [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 순으로 배열된 배열에서 각각의 숫자를 포함하거나 포함하지 않는 경우를 기준으로 브루트포싱을 해주면 순회 횟수가 2^10 밖에 되지 않으므로 무난하게 해결할 수 있..