문제 링크 1. 문제 풀이 자연수들로 이루어진 집합 $U$ 에서 고른 세 수의 합이 $U$ 에 포함되는 가장 큰 수를 찾는 문제다. $N$ 이 최대 $1,000$ 이어서 3중 반복문을 통한 풀이는 시간 초과가 발생하게 되는데 이를 2중 반복문 두 개로 쪼개서 해결하는 중간에서 만나기를 적용해야 한다. 핵심은 $a + b + c = d$ 를 ...

문제 링크 1. 문제 풀이 주어진 수열에서 임의의 두 수의 차가 $M$ 이상이면서 제일 작은 경우를 구해야 하는 문제로 두 수가 같아도 된다. $N$ 이 최대 $100,000$ 이라서 $O(N^2)$ 으로는 풀 수 없는데 투 포인터를 활용하면 해결할 수 있다. 먼저 주어진 수열을 오름차순으로 정렬한다. 이후 두 포인터를 앞에서부터 출발시켜...

문제 링크 1. 문제 풀이 주어진 $1$ 일 ~ $N$ 일 중 연속된 $X$ 일에 대해 방문자 수가 최대인 순간의 값을 구하고 그런 구간의 개수를 출력하되, 최대 방문자 수가 $0$ 이면 SAD를 출력해야 하는 문제다. $N$ 이 최대 $250,000$ 이어서 $O(N^2)$ 으로는 해결할 수 없어 효율적인 탐색이 필요하다. 구간의 합을 빠...

문제 링크 1. 문제 풀이 $N$ 개의 눈덩이 중 $4$ 개를 사용하여 두 눈사람의 키 차이가 최소가 되게 해야 한다. 정렬과 투 포인터를 활용하면 해결할 수 있는데 먼저 정렬을 통해 눈덩이가 오름차순이 되게 해준다. 이후 2중 반복문을 통해 한 쪽 눈사람을 만들 두 눈덩이를 고른 후 고른 두 눈덩이의 사이에 있는 눈덩이로 반대쪽 눈사람을 ...

문제 링크 1. 문제 풀이 구간합이 $M$ 이 되는 경우의 수를 세는 문제로 구간합을 효율적으로 구할 수 있는 누적 합을 활용하거나 투 포인터를 활용하면 해결할 수 있다. 2. 코드 1. 누적 합 [Java] import java.io.*; import java.util.*; public class Main { publ...

문제 링크 1. 문제 풀이 주어진 4자리 소수에 대해 특정 자리를 바꾸는 과정을 반복해서 다음 소수를 만들어야 하는 문제다. 이때 바꾸는 과정도 전부 소수여야 한다. 에라토스테네스의 체를 활용해 4자리 소수를 전부 구한 후 BFS를 통해 각 자리를 바꿨을 때, 소수이면 계속 탐색하고 아니면 탐색하지 않는 방향으로 해결할 수 있다. 2....

문제 링크 1. 문제 풀이 서로 다른 $N$ 개의 자연수의 합이 $S$ 일 때, $S$ 를 알려주고 $N$ 의 최댓값을 구하는 문제다. $N$ 이 최대한 커지려면 최대한 작은 자연수로 $S$ 의 합을 이루면 되며 이는 $1$ 부터 쭉 더해나가면 된다. $1$ 부터 연속한 자연수의 합인 $\dfrac{n \times (n+1)}{2}$ 을 활...

문제 링크 1. 문제 풀이 주어진 $K$ 개의 랜선을 적절한 길이로 잘라서 같은 길이를 갖는 $N$ 개 이상의 랜선을 만들어야 하는 문제다. 자를 길이를 길이 $1$ 부터 쭉 브루트 포스로 접근하면 탐색 범위가 너무 넓어서 시간 초과가 발생하기 때문에 효율적인 접근이 필요한데 매개 변수 이분 탐색을 활용하면 해결할 수 있다. $N$ 개 이...

문제 링크 1. 문제 풀이 주어진 수를 소수의 연속된 구간의 합으로 나타낼 수 있는 경우의 수를 구하는 문제로 에라토스테네스의 체를 활용해 소수들을 얻은 후 투 포인터를 적용하면 간단하게 해결할 수 있다. 2. 코드 1. 풀이 [Java] $N = 1$ 이면 소수 리스트가 아예 비어있어서 예외 처리를 해줬다. import ja...

문제 링크 1. 문제 풀이 주어진 $N$ 개의 과자를 $M$ 명의 조카에게 나눠줄 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구해야 하는 문제다. 이때 과자 길이는 동일해야 하며 합칠 수 없다. 해당 문제는 매개 변수 이분 탐색을 활용하면 해결할 수 있는데 과자 길이의 하한과 상한의 중간 값을 기준으로 과자를 나눠줄 수 있는...