DivideAndConquer

https://www.acmicpc.net/problem/1493 코드import sysinput = sys.stdin.readlinel, w, h = map(int, input().split())n = int(input())cubes = []for _ in range(n): a, b = map(int, input().split()) cubes.append([2**a, b])def dc(l, w, h, idx): # 분할정복 if idx == -1: # 큐브 부족 print(-1) exit() res = 0 # idx번째 큐브의 필요 개수 need = (l//cubes[idx][0])*(w//cubes[idx][0]) * (h//cubes[..

5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 코드 n = int(input()) def dc(k, l, n): # K, S(K)의 길이, 구하는 순서 N if n n: break k += 1 print(dc(k, l, n)) 분할정복을 이용하여 Moo 수열의 N번째 문자를 구한다. 큰 수열에서 작은 수열로 분할하는 방식을 쓸 것이므로 n이 포함되는 가장 최소의 S(k)수열을 먼저 구한다. S(k)의 길이 = S(k-1)의 길이+k+3이므로 이걸 이용하면 n이 포함되는 가..

1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 코드 def dc(arr): if len(arr) == 1: return True mid = len(arr)//2 for i in range(mid): if arr[i] == arr[len(arr)-1-i]: return False return dc(arr[:mid]) and dc(arr[mid+1:]) for _ in range(int(input())): fold = input() print("YES" if dc(fold) else "NO")

4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자. 1. -가 $3^N$개 있는 문자열에서 시작한다. 2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다. 3. 이제 각 선(문자열)을 3등분 하고, 가운데..

1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 문제 프렉탈 평면은 다음과 같이 커진다. 시간 0에서 프렉탈은 흰색 정사각형 하나이다. 단위 시간(1)이 진행될 때마다 N×N개의 크기가 동일한 단위 정사각형으로 나누어진다. 만약 나누어진 정사각형이 흰색이라면 가운데 K×K 정사각형이 검정색으로 채워진다. N과 K는 둘 다 홀수이거나, 둘 다 짝수이다. 예를 들어, N=3, K=1이라면, 시간 1에 3×3 정사각형이 된다. 가운데 정사각형은 검정색이고, 나머지는 흰색이 된다. 시간 2때 9×9 정사각형이 되고, 17개는 검정이고, 나머지는 흰색이다. s, N, K, R1, R2, C1, C2가 주어질 때, 시간 s일 때, ..