https://www.acmicpc.net/problem/30804 탕후루 꼬치에서 앞 뒤로 몇개의 과일을 빼 2가지 종류 이내로 구성된 가장 긴 길이의 탕후루 꼬치를 만드는 문제다.처음에는 단순 구현을 해야하나 싶어서 한참 고민했는데, 앞 뒤로 과일을 뺀다는 것은 남은 과일이 연속적이라는 점에서 힌트를 얻어 투 포인터를 생각해낼 수 있었다. 앞에서부터 과일을 하나씩 살펴보면서 2가지 종류가 되지 않았다면 연속된 길이에 포함하고, 2가지가 넘는 종류가 나오는 순간 그때까지 담은 길이를 정답 후보로 체크한다.그리고 그 이전에 담았던 과일 중, 제일 마지막에 나왔던 종류가 아닌 과일을 2가지 종류에서 제외하고, 새로 나온 종류를 2가지 종류에 추가한 뒤 위 과정을 반복한다. n = int(input())fr..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나는 투포인터를 안쓰고 풀었는데, 정해가 투포인터라서 놀랐다. 확실히 '어떤 정렬된 것들중 일부의 연속' 은 투포인터를 쓰기 좋다. 일단 이 문제가 골드3이라서 당연히 DP부터 의심했는데, DP가 아닌 풀이가 떠올라서 바로 구현했다. 내가 푼 풀이와 투포인터 풀이를 모두 적어보겠다. 이분탐색을 이용한 풀이 소수의 리스트 2, 3, 5, 7, 11, 13, ,,,, 가 있다고 하고 소수의 누적합 배열을 s 라고 해보자. (누적합 배열은 0부터 시작한다고 하자) 최적해가 되는 구간은 어떤 소수로 시작할 것이다. 2로 시..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 여러가지 방법으로 풀 수 있는 세 용액 문제이다. 나는 처음에 이분탐색을 시도 했다가 막혔는데, 구현을 쓸데없이 복잡하게 하다가 실수를 했던 것 같다. 2시간 고민하다가 다른 이분탐색 풀이 알고리즘을 보고 수정하여 맞았다. 이 문제를 투 포인터로 풀 수 있겠다는 생각까진 해봤는데, 구체적으로 어떻게 투 포인터를 써야할 지 떠오르지가 않았다. 그렇게 공부하여 알게된 알고리즘이 ..
