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

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

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

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

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

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

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

문제 링크 1. 문제 풀이 길이 $64$ 인 막대기를 가지고 길이 $X$ 인 막대기를 만들어야 하는데 현재 가지고 있는 막대기의 길이의 합이 $X$ 보다 크면 가지고 있는 막대기 중 길이가 가장 짧은 것을 절반으로 자르고, 자른 막대기 중 하나를 버리고 남은 막대기의 길이의 합이 $X$ 보다 크거나 같다면 자른 막대기 중 하나를 버리는 과정을 ...

문제 링크 1. 문제 풀이 행렬의 거듭제곱을 구하는 문제로 $B$ 의 크기가 최대 $100,000,000,000$ 이어서 단순한 행렬 곱셈의 반복으로는 해결할 수 없다. 행렬의 곱셈은 결합법칙이 성립한다는 점에서 이진 거듭제곱을 적용하면 해결할 수 있다. 최종 결과 행렬의 각 원소를 $1,000$ 으로 나눈 나머지를 출력해야 하는데 나머지 연...

문제 링크 1. 문제 풀이 $N$ 가지 동전을 무한히 사용할 수 있을 때 그 합이 $M$ 이 되는 경우의 수를 구하는 문제다. 일종의 무한 배낭 문제로 여기서는 최댓값이 아닌 모든 경우의 수를 구해야 한다. 경우의 수는 현재 동전을 고려하는 상황에서 현재 동전을 사용하지 않을 경우 이전 동전들로만 만들 수 있었던 경우의 수만큼은 만들 수 있다...