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

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

문제 링크 1. 문제 풀이 BaekJoon 3067번 - Coins 문제와 완전히 동일하다. 2. 코드 1. Bottom-Up 2차원 dp [Java] import java.io.*; import java.util.*; public class Main { public static void main(String[] arg...

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

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

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

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

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

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

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