본문 바로가기

Two Pointer6

[백준/C++] #20366 같이 눈사람 만들래? (Two Pointer) 문제https://www.acmicpc.net/problem/20366구상N개의 눈덩이를 가지고, 4개의 눈덩이를 골라, 2개의 눈사람을 만드는데, 두 눈사람의 높이의 차가 최소가 되도록 하여 최소인 높이 차를 출력하는 문제였다. 지금보면 진짜 바보같지만, 처음에는 진짜 내가 이걸 1초만에 생각해낸게 신기할 정도로 쉬워보이는 풀이 (결과적으로 틀린 풀이) 를 생각해냈다.  무엇이었냐 하면, 눈사람의 지름이 a, b, c, d라 하면, (a+b) - (c+d)의 값이 가장 작으면 되니까, (a-c)-(d-b)의 최소값을 구하면 되겠다 생각해서 눈사람의 지름 오름차순으로 정렬하고, 인접한 배열의 값끼리의 차를 구한 배열을 만들어서, 그걸 또 정렬해서(인덱스 값과 함께 pair로. 인접한것 고르면 안되니까),.. 2024. 7. 22.
[백준/C++] #16472 고냥이 (Two Pointer) 사실 어렵거나 함정이 있는 문제는 아니었는데... 그냥 문제 이름이 너무 귀여워서 포스팅한닷문제https://www.acmicpc.net/problem/16472구상최대 N개의 종류의 알파벳을 가진 연속된 문자열의 최대 길이를 구하는 문제였다. "연속된" 문자열의 길이라고 하니까 투 포인터로 접근할 수 있겠다 싶었다. 문자열의 인덱스값을 가리키는 lett와 right를 0부터 쭉쭉 나아가면서 left~right까지 사용하는 알파벳을 확인하면서 값 갱신하면 될듯했다.  알고리즘두개의 포인터를 이용하여 문제를 푸니까 Two pointer!! 풀이 + 코드1. 사용하는 알파벳이 N개 미만이거나 N개라면, 값 비교후 갱신하고, right ++, 개수 확인2. 사용하는 알파벳이 N개 초과라면, left++, 개수.. 2024. 7. 22.
[백준/C++] #2473 세 용액 (Two Pointer) 문제https://www.acmicpc.net/problem/2473 구상세 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어야 하고, 이때의 세 용액을 출력해야 하는 문제였다. 두 용액 일 때는 아래와 같이 두개의 포인터를 이용해서 풀었었다. https://persi0815.tistory.com/entry/%EB%B0%B1%EC%A4%80C-2467-%EC%9A%A9%EC%95%A1-Two-Pointer 세 용액이면 어떡할까? 고민을 해봤는데, 한 용액을 고정한 뒤 나머지 두 용액을 투 포인터로 찾는 방법이 떠올랐다.  알고리즘: two pointer 풀이 + 코드용액 특성값들을 배열에 넣고 투포인터 사용을 위해 정렬을 했다. 그리고, 한 용액을 선택한 뒤, 나머지 두 용액을 결정하자. brut.. 2024. 7. 3.
[백준/C++] #2467 용액 (Two Pointer) 문제https://www.acmicpc.net/problem/2467   알고리즘: two pointer 풀이 + 코드가장 기초적인 투포인터 문제다.(정렬된) 용액 특성들을 배열에 넣고, 두개의 포인터를 이용하여 배열 값들의 합을 구하며 0과 가장 가까운 값이 나타나면 답을 갱신한다.  #include #include #include #include #define MAX 100001#define INF 987654321#define endl "\n"using namespace std;/*2467번 용액산성 용액: 1부터 1,000,000,000, 알칼리성 용액: -1부터 -1,000,000,000같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합같은 양의 두 용액을 혼합하여.. 2024. 7. 3.

티스토리툴바