투 포인터 썸네일형 리스트형 BOJ)14943 벼룩 시장 문제: icpc.me/14943벼룩을 사려는 사람과 팔려는 사람이 있을 때 벼룩 거래에 발생하는 비용의 최솟값을 출력하는 문제이다.문제를 잘 읽어보면 사려는 양과 팔려는 양은 같고, 거래에 발생하는 비용이 거래하는 두 사람의 거리에 비례한다.우선 사려는 양과 팔려는 양이 같다는 점을 이용해, 항상 거래가 완전하게 이루어진다는 점을 생각해보면, 그냥 최대한 가깝게 거래를 매칭 시켜주는 그리디한 방법이 답이 된다는 걸 알 수 있다.문제는 n이 10만으로 조금 크기 때문에 매칭을 일일이 직접 해줄 수는 없고, 투 포인터를 이용하여 처리해주면 깔끔하게 구현 가능하다.1234567891011121314151617181920212223242526272829303132333435363738#include #inclu.. 더보기 BOJ)1322 X와K 문제: icpc.me/1322 X가 정해져 있을 때 X+Y = X | Y 를 만족하는 Y는 2진수에서의 연산을 생각한다면 X가 0인 비트에만 1이 채워져있는 수일 것이다. 고로 K번째로 큰 Y를 찾는다면 K를 이진수로 표현하였을 때 1이 채워진 순서를 X에서 0인 부분에 순서대로 채운 수가 된다. 이는 투 포인터로 구해줄 수 있다. 12345678910111213141516#include #include using namespace std;typedef long long ll;ll x, y, k;int main() { scanf("%lld%lld", &x, &k); for (int i = 0, j = 0; j 더보기 BOJ)2230 수 고르기 문제: icpc.me/2230 N개의 원소로 이루어진 수열에서 두 수를 뽑았을 때 그 수의 차이가 M보다 크면서 가장 작은 두 수의 차이를 구하는 문제이다. 우리는 정렬을 해준 뒤 투 포인터 i , j 를 설정하여 문제를 해결할 수 있다. a[i]-a[j]가 m보다 작다면 두 수의 차이가 더 커져야 하므로 i를 증가시키고 m보다 크거나 같다면 j를 증가시키는 방법으로 해결해나가면 된다. 1234567891011121314151617181920212223#include #include #define INF 1987654321using namespace std;int n, m, a[100001], r;int main() { scanf("%d%d", &n, &m); for (int i = 0; i 더보기 이전 1 다음