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

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

문제 링크 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$ 이면 소수 리스트가 아예 비어있어서 예외 처리를 해줬다...

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

문제 링크 1. 문제 풀이 문자열 $S$ 안에 문자열 $W$ 의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 세는 문제로 $g$ 의 범위가 최대 $3,000$, $S$ 의 길이가 최대 $3,000,000$ 이라서 효율적인 탐색이 필요하다. 슬라이딩 윈도우를 기본으로 현재 윈도우에 대한 카운팅 배열을 적용하면 해결할 수 있다. ...

문제 링크 1. 문제 풀이 주어진 문자열에서 최소 교환 횟수로 $a$ 가 연속이 되게 해야한다. 이때 교환은 두 문자의 위치를 바꾸는 것이다. 문자열의 양 끝은 원형으로 연결되어 있다. 예제 입력 1을 예로 들자면, 주어진 문자열은 아래와 같다. 표시된 두 문자를 교환한다. 표시된 두 문자를 교환한다. 표시된 두 문자를...

문제 링크 1. 문제 풀이 주어진 문자열에 대해 고정된 길이의 임의의 구간이 비밀번호의 조건을 만족하는 경우의 수를 구하는 문제다. 조건은 구간이 각 문자를 특정 개수 이상 포함해야 한다. 문자열과 구간의 최대 길이가 $1,000,000$ 이라는 점에서 $O(N^2)$ 풀이는 시간 초과가 발생하는데 슬라이딩 윈도우를 활용하면 해결할 수 있다. ...