투포인터5 BOJ 2531 - 회전 초밥 2531번: 회전 초밥 (acmicpc.net) 접근 방법초밥을 연속 K를 먹었을 때, 먹을 수 있는 가장 많은 가짓 수를 선택하는 문제이다.이 문제에서 주의 깊게 봐야할 것이 쿠폰이다. 처음에 쿠폰이 해당 쿠폰의 초밥을 먹을 때, 추가로 1개를 더 먹는 거라고 착각했다.그러나 이 문제에서 " 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다." 를 고려하지 않은 문제풀이이다. 따라서, 해당 쿠폰의 초밥을 안 먹은 경우 가지 수를 1가지 추가하고 슬라이딩 윈도우를 하면 된다. 코드#include #include #include #define ll long longusing namespace std;int n, d, k, c;vector v;int selec.. 2024. 4. 29. BOJ 2473 - 세 용액 2473번: 세 용액 (acmicpc.net) 2473번: 세 용액첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상www.acmicpc.net 접근 방법용액 문제와 비슷하게 해결 가능한 투 포인터 문제이다.세 용액의 합이 0에 가장 가까운 용액들을 고르는 문제이기 때문에 처음엔 두 개의 용액을 모두 더 한 배열을 이용하여, 나머지 용액을 투포인터로 선정하는 방법을 사용했다. struct st{ int a; // 용액A int b; // 용액B int sum; // 용액A + 용액B}위 구.. 2024. 4. 23. BOJ 1644 - 소수의 연속합 1644번: 소수의 연속합 (acmicpc.net) 접근 방법 투 포인터와 소수판별 알고리즘이 혼합된 문제이다. 소수 판별을 하기 위해 에라스토테네스의 체를 이용하여 소수를 배열에 저장한다. 해당 소수 배열을 투포인트를 돌면서 각 연속적인 수들의 합이 N이 될 때, 경우의 수를 + 1한다. 코드 #include #include #include using namespace std; #define MAX 4000001 #define ll long long bool chk[MAX+3]; vector arr; ll n, s; void func() { chk[1] = true; for (int i = 2; i < MAX; i++) { if(!chk[i]) arr.push_back(i); for (int j = i.. 2024. 4. 23. BOJ 1806 - 부분합 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 접근 방법 연속된 수들 중 합이 S 이상인 것들의 길이가 최소인 것을 구하는 문제이다. 전형적인 투포인터 유형의 문제로 쉽게 해결 할 수 있다. 문제에서 주의할 점이 S이상 이기 때문에 이 또한 고려해야 한다. 또한, 수의 범위가 꽤 크기 때문에 자료형 선정 시도 고려해야 한다. #include #include #include using namespace std; #define MAX 100001 #de.. 2024. 4. 23. BOJ 2230 - 수 고르기 2230번: 수 고르기 (acmicpc.net) 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 접근 방법 이분 탐색으로 이 문제를 해결하려고 했다. 두 수를 고르는 것이기 때문에 하나(i)를 for을 돌면서 각 수 위에서부터 끝까지(i+1~n) 수를 이분탐색을 하면서 돌면된다고 생각. 이분탐색의 경우, 하나를 모두 돌면서 진행되므로 O(N*logN)이 수행되지만, 이를 투포인터를 이용할 경우, 모든 수를 한 번씩만 돌기 때문에 O(N)에 수행이 가능하다. 따라서, 투포인터가 더 빠른 실행.. 2024. 4. 22. 이전 1 다음
