문제 링크 1. 문제 풀이 numbers의 길이가 최대 100,000이라서 주어진 정수들을 이어 붙인 모든 조합을 찾는 방식으로는 해결할 수 없다. 이 문제는 정렬을 활용하면 해결할 수 있는데 numbers의 임의의 두 수 num1, num2에 대해 num1 뒤에 num2를 붙인 수와 num2 뒤에 num1을 붙인 수를 비교해 전자가 크면 ...

문제 링크 1. 문제 풀이 활성화된 앱들이 주어져 있고 각 앱은 비활성화 했을 때, 비용 $c$ 와 확보할 수 있는 메모리 $m$ 을 가지고 있다. 이때 $M$ 이상의 메모리를 확보할 때 최소 비용을 알아내야 하는 문제다. 이는 비용을 무게, 확보할 수 있는 메모리를 가치로 간주하는 0/1 배낭 문제 로 해결할 수 있다. 각 앱을 비활성화하...

문제 링크 1. 문제 풀이 슈퍼 마리오가 얻은 점수가 $100$ 에 최대한 가깝게 하는 문제로 가까운 수가 2개면 큰 값을 선택해야 하며, 버섯은 안먹은 순간부터 뒤에 나오는 버섯은 전부 먹을 수 없다. 그냥 조건문 기반으로 구현하는 방식으로 해결해도 되고 누적 합을 활용해서 해결해도 된다. 2. 코드 1. 구현 [Java] i...

문제 링크 1. 문제 풀이 주어진 추들을 활용해 양팔저울에서 구슬의 무게를 측정할 수 있는지 여부를 구하는 문제다. 배낭 문제를 응용한 문제로 추들의 조합으로 특정 무게를 맞출 수 있는지 여부를 찾아야 한다. 구슬의 무게를 측정하는게 구슬 반대편에 추들을 배치하는 식으로 추들의 무게의 합으로 측정할 수도 있지만 구슬이 있는 쪽에 일부 추를 ...

문제 링크 1. 문제 풀이 내려가기 게임에서 이동 가능한 경로는 현재 위치에서 바로 아래 칸이거나 대각선 칸으로만 이동할 수 있다. $0$ 번 인덱스 위치에서는 $0$, $1$ 번 인덱스로, $1$ 번 인덱스 위치에서는 $0$, $1$, $2$ 번 인덱스로, $2$ 번 인덱스 위치에서는 $1$, $2$ 번 인덱스로 이동할 수 있다. 이때 얻...

문제 링크 1. 문제 풀이 주어진 문자열에 대해 특정 문자를 $K$ 개 포함하는 구간의 길이의 최솟값과 특정 문자를 $K$ 개 포함하면서 구간의 양 끝 문자가 같은 구간의 길이의 최댓값을 구하는 문제다. 각 문자의 등장 위치를 문자별로 구분해서 저장한 후 각 문자의 등장 위치들에 대한 슬라이딩 윈도우를 활용하면 해결할 수 있다. super...

문제 링크 1. 문제 풀이 모든 몬스터를 쓰러트리기 위한 용사의 최대 생명력을 찾아야하는 문제로 매개 변수 탐색을 활용하면 간단하게 해결할 수 있다. 주어진 던전 정보를 통해 필요한 체력을 계산하는 것이 아니라 체력의 하한과 상한을 정하고 그 중간값으로 던전을 돌아보고 안되면 체력을 증가시키고 되면 체력을 감소시켜가며 던전을 돌 수 있는 최...

문제 링크 1. 문제 풀이 $+$, $-$, $0$ ~ $9$ 로 이루어진 문자열에서 괄호를 적절하게 쳐서 식의 최솟값을 만들어야 하는 문제로 연산자는 연속으로 두 개 이상 나타나지 않고 가장 처음과 마지막 문자는 숫자이다. 괄호를 어떻게 쳐야 식이 최솟값이 되는지가 중요한데 괄호 앞에 $-$ 가 붙으면 괄호 안의 연산자가 뒤바뀐다는게 포인...

문제 링크 1. 문제 풀이 $T$ 분 동안 $N$ 개의 문제 중 어떤 문제를 어떤 순서로 풀어야 점수가 최대가 될지 찾는 문제다. 각 문제가 주는 점수가 고정되어 있다면 0/1 배낭 문제 를 활용해서 해결할 수 있는데 문제가 주는 점수가 유동적이라서 일반적인 방법으로는 안된다. 핵심은 배낭에 담되 어떤 순서로 담아야 최댓값이 되느냐인데 $...

문제 링크 1. 문제 풀이 일종의 무한 배낭 문제 로 $C$ 명 이상 확보할 수 있는 최소 비용을 찾아야 하는 문제다. 배낭을 고객으로 가치를 비용으로 설정한 배낭에서 배낭 크기가 $C$ 이상인 상황 중 배낭 가치가 최소일 때를 찾으면 된다. 이때 정확히 $C$ 명을 찾았을 때 비용이 최소가 아니라 $C$ 명 보다 큰 어느 순간 비용이 최소...