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

문제 링크 1. 문제 풀이 거스름돈을 줄 때 동전의 개수가 최소가 되게 해야하는 문제다. 동전의 액면가가 전부 배수 관계에 있기 때문에 액면가가 더 큰 동전을 최대한 많이 거슬러주면 된다. 2. 코드 1. 그리디 알고리즘 [Java] import java.io.*; public class Main { public static ...

문제 링크 1. 문제 풀이 $n$ 이 최대 $2^{63} - 1$ 일 때, $q^2 \ge n$ 을 만족하는 가장 작은 자연수 $q$ 를 찾는 문제로 이분 탐색 + 매개 변수 탐색을 활용하면 해결할 수 있다. $q$ 는 $0$ 이상 $n$ 의 제곱근 $+1$ 사이에 존재하므로 해당 구간에 대한 Lower Bound 이분 탐색을 적용했다.($2^...

문제 링크 1. 문제 풀이 $n$ 가지 동전을 적당히 사용해서 가치의 합이 $k$ 원이 될 때, 사용한 동전의 개수가 최소가 되는 경우를 찾는 문제로 동전을 여러 번 사용할 수 있으니 무한 배낭 문제로 해결할 수 있다. 배낭의 크기가 현재 동전의 가치보다 작다면 담을 수 없고, 현재 동전의 가치보다 크거나 같다면 안 담는 경우와 담는 경우 중 ...

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

문제 링크 1. 문제 풀이 소의 스티커의 부호를 여러 번 바꿀 수 있을 때 $S$ 를 구하는 문제로 주어진 쿼리의 수가 많아서 효율적으로 $S$ 를 구할 수 있어야 한다. 연속한 네 마리의 품질 점수의 곱을 미리 저장한 후 이를 활용하는 방식으로 계산량을 줄일 수 있다. 2. 코드 1. 구현 [Java] import java.io.*;...

문제 링크 1. 문제 풀이 최대 $M$ 만큼의 무게를 넣을 수 있는 배낭이 있고 각 물건이 여러 개 존재할 때 만족도의 최댓값을 찾는 문제다. 물건의 종류가 $N$ 이고, 각 물건의 개수가 $K$ 개인데 둘의 곱이 최대 $1,000,000$ 이고 $M$ 도 최대 $10,000$ 이어서 각 물건 하나하나마다 0／1 배낭 문제를 적용하면 시간 내에...

문제 링크 1. 문제 풀이 최대 $K$ 만큼의 무게를 담을 수 있는 배낭에 주어진 물건들을 담을 때 물건의 가치의 합이 최대가 되게 하는 문제다. 물건의 수가 최대 $100$ 개로 각 물건을 담거나 안담는 브루트 포스로는 경우의 수가 $2^{100}$ 으로 시간 초과가 발생한다. 문제 설명부터 힌트가 있는데 각 물건을 담거나 안담는 두 가지 경...

문제 링크 1. 문제 풀이 주어진 동전들을 적절히 사용해서 가치의 합이 $K$ 가 될 때 필요한 동전 개수의 최솟값을 구하는 문제다. 각 동전을 여러 번 사용할 수 있으며 동전의 가치가 오름차순으로 주어지고 서로 배수 관계에 있으므로 최대한 가치가 큰 동전부터 많이 사용하면 된다. 사용한 동전의 개수는 가치로 나눈 몫이 되며 나머지에 대해 다음...

1. 이진 거듭제곱 이진 거듭제곱(Binary Exponentiation, Exponentiation by Squaring)은 $a^n$ 연산의 결과를 $O(\log{n})$ 의 시간복잡도로 해결하는 알고리즘이다. $a^n$ 은 $a$ 를 $n$ 번 곱한 수이므로 반복문을 활용해 $a \times a \times \cdots \times a$ 처럼...