백준 20366번 N의 범위가 4~600이니까 범위가 상당히 작고 O(N^3)까지는 문제를 통과할 수 있다. 그럼 두 눈사람을 잡고 그 사이의 눈사람들에 대해 투포인터를 이용하면 된다. 두 눈사람을 잡는 과정은 for문 2개이고, 그 사이의 눈사람들을 잡는건 아무리 많아봐야 O(N)이 된다. 그래서 최대 O(N^3)에 문제를 해결할 수 있다. 백준/투포인터 2022.02.07
백준 2283번 다뤄야될 변수가 좀 많아서 번거로웠다. a, b, l, sp, ep, st, en이 있고 st와 en은 앞에서 했던 방식과 마찬가지로 투포인터 시작과 끝점을 나타낸다. l은 st와 en으로 둘러싸였을 때 잘려진 구간의 길이 합이다. sp는 구간 n개의 시작점의 개수를 나타내고 ep는 구간 n개의 끝점의 개수이다. a, b는 각각 st와 en이 각 구간에 포함된 개수를 나타낸다. 백준/투포인터 2022.02.06
백준 2461번 입력을 능력치와 반으로 묶은 pair로 받고, 이를 sort해준다. 그 후 st와 en 사이에 n개의 반 학생이 1명이라도 다 들어갈 경우의 최대값과 최소값의 차이를 구해주고 이를 계속 갱신해주면 된다. 백준/투포인터 2022.02.06
백준 13144번 설 연휴라 잠깐 쉬고 오랜만에 올리게 되었다! 글을 다 쓰고 다시 확인해보니 위 코드 가운데 if (st < en) 문은 빼고 그냥 cnt += en-st만 해줘도 코드가 잘 돌아간다. st가 en보다 커질 수가 없고 같으면 그냥 0이 더해지는 효과니까 사실상 같다. 백준/투포인터 2022.02.03
백준 1644번 투포인터를 이용하여 풀었다. 우선 에라토스테네스의 체 방식으로 1~n까지의 소수들을 파악하고, 그 다음 소수들을 primes 벡터에 넣어서 투포인터를 사용하였다. 시간 복잡도는 에라토스테네스의 체 시간복잡도인 O(nloglogn)이다. 누적합에 대한 이분탐색으로도 풀 수 있다. 대부분의 투포인터 문제는 이분탐색으로도 풀 수 있는 것 같다 ! 백준/투포인터 2022.01.28