728x90 분할 정복5 [JAVA]백준 10830번: 행렬 제곱 www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 문제 설명 크기가 N*N 행렬 A가 주어질 때 A의 B제곱을 구하는 문제이다. 답은 각 원소를 1000으로 나눈 나머지를 출력한다. 2. 풀이 B의 범위가 1 2021. 4. 8. [JAVA]백준 5904번: Moo 게임 www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 1. 문제 설명 문자열 S(k)는 S(0)="moo", S(k)=S(k-1)+m+o가 k+2개+S(k-1)인 문자열이다. N이 주어졌을 때, S(k)의 N번째 글자를 구하는 프로그램을 작성하는 문제이다. N을 분할해 나가면서 문제를 해결하였다. 먼저 최초로 N보다 큰 문자열의 길이를 구한다. 구한 문자열이 S(X)라고 할 때, S(X)=S(X-1)+m+o가 X+2개+S(X-1.. 2021. 1. 2. [JAVA]백준 1725번: 히스토그램 www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 1. 문제 설명 주어진 히스토그램에 대해 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하는 문제이다. 종만북의 분할 정복 예시 문제 울타리 잘라내기 문제와 같은 문제이다. 종만북의 풀이과정 같이 3가지의 형태로 문제를 분할하여서 풀었다. 막대그래프를 반으로 잘랐을 때 가장 큰 직사각형은 3가지의 경우로 존재할 수 있다. 1. 가장 큰 직사각형은 왼쪽 그래프에만 있을 경우 2. 가.. 2021. 1. 2. [JAVA]백준 4779번: 칸토어 집합 www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 1. 문제 설명 -로 채워진 입력받은 수의 길이의 문자열을 만든 후 선의 길이가 1이 될 때까지 3 등분하고 가운데 문자열은 공백으로 바꾼다. 먼저 char 배열 전체를 공백으로 바꾸고 range가 1이 될때까지 삼등분하면서 재귀 호출하였다. 2. 코드 import java.awt.image.BufferedImageFilter; import java.io.*; import java.lang.reflect.Arr.. 2020. 12. 28. 이전 1 2 다음 728x90
