백준 : 분할정복

https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 입력 첫째 줄에 세 자연수 length width height가 주어진다. 둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다. 셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다. 예제 입출력을 살펴보자. 예제 입력 1 복사 4 4 8 3 0 ..

https://www.acmicpc.net/problem/16974 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 레벨 버거와 먹은 햄버거의 수가 주어졌을 때 먹은 패티의 양을 구하는 문제이다. 레벨 버거는 빵 + 이전단계 레벨버거 + 패티 + 이전단계 레벨버거 + 빵으로 구성된 버거이다. 레벨0 버거는 패티한장만으로 구성되 있다고 한다. 수식으로 만들면 다음과 같이 만들 수 있다. B (Li - 1) p (Li - 1) B 그럼 예제를 분석해보자. 예제 입력 1 복사 2 7 레벨 2 버거를 7..

https://www.acmicpc.net/problem/1030 1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 이문제는 s,N, K, R1, R2, R3, R4를 입력받은 뒤 범위만큼의 프렉탈 크기를 출력하면된다. s = 반복횟수 N = 프렉탈의 크기 K = 검은색(1) 크기 R1, R2 = 행의 크기 C1, C2 = 열의 크기 예제를 보면서 설명하겠다. 예제 입력 1 복사 1 5 3 0 4 0 4 예제 입력 2 복사 2 3 1 0 8 0 8 예제 입력 3 복사 3 3 1 4 11 5 10 import java.util.Scanner; public class 프렉탈평면 { static int s, N, K, R1, R..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net NxN 색종이를 입력받은 후 정사각형이 될 때까지 나눈다. 그리고 최종적으로 나누어진 하얀색, 파란색 색종이의 개수를 출력하면 되는 문제이다. 입출력을 살펴보자. 8 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이문제는 행렬의 지수를 절반으로 자르면서 분할계산을 하는 행렬 제곱문제이다. 분할 계산(partition) 문제를 풀기위해서는 짝수일 경우, 홀수일 경우 어떻게 숫자를 탐색해야 하는지 생각해 봐야한다. 먼저 짝수일 경우 계산 과정이다. 위에서 설명했다시피 분할 계산을 해주면 되는데 짝수일 경우는 2로 나누었을 때 나머지가 생기지 않으므로 그냥 나누어서 곱해주면 된다. 다음은 홀수인 경우이다. 홀수의 경우 2로 ..