문제풀이: https://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 다루는 주제: 분할정복 # n 에서 전차수를 뺄때 1이면 n return은 m이다 나머진 전부 o # 새로운 차수 = S(k-1) + oxk+m + S(k-1) 새로운차수 길이 = 전차수 + 3 + 전차수 # n이 l보다 크고 다음 차수로 가는 필요길이보다 작을때만 # +++ l다음 글자는 무조건 m이다 import sys def moo(n, k, l..
문제링크:https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 다루는 주제: 이분 탐색 import sys def binary(arr, start, end): result = 0 while start middle: # 나무길이가 중간값보다 크면 total += tree - middle # 나무길이 - 중간값 즉 가져갈 나무길이를 total에 저장 if total < M: # 가져갈 나무길이의 총합이 M에 미치지..
문제링크:https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 다루는 주제: 스택 import sys # 탑의 수 N = int(sys.stdin.readline()) # 탑의 높이 tops = [0] + list(map(int, sys.stdin.readline().split())) result = [0] * (N + 1) stack = [] for i in range(1, N + 1): # Stack에 탑의 정보가 남아있다면 while stac..
문제링크:https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 다루는 주제: 분할정복 import sys N, B = map(int, sys.stdin.readline().split()) # N*N행렬 입력 , B만큼 제곱 A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 행렬 받기 # NxN 행렬 곱셈 함수 def multiplication(n, a, b): result = [[0] *..
문제링크:https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 다루는 주제: 분할정복 import sys def histo(arr, start, end): if start == end: return arr[start] else: mid = (start + end) // 2 width = 2 # 너비 left = mid # 경계 왼쪽 right = mid + 1 # 경계 오른쪽 min_heigh..
문제링크:https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 다루는 주제: 분할 정복 import sys A, B, C = map(int, sys.stdin.readline().split()) # A * A * A * A ... * A % C로 문제를 풀고자 했으면 시간 초과 # A**B%C를 (A**B//2) * (A**B//2) * C 이런식으로 곱셈 계산을 최소화 def calc(a, b): if b == 1: return a % C else: temp = calc(a, b // 2) # ex) 10^10 ..
문제풀이:https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 다루는 주제: 분할 정복 import sys N = int(sys.stdin.readline()) square = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] white = 0 blue = 0 def cut(row, column, n): global white, blue color = squ..
문제링크:https://www.acmicpc.net/problem/8983 import sys # 첫줄 입력 M은 사대의 수 N은 동물의 수 L은 사정거리 M, N, L = map(int, sys.stdin.readline().split()) # 두 번쨰 줄 입력은 사대의 좌표 입력 saro = list(map(int, sys.stdin.readline().split())) # 그 이후 줄들은 동물의 좌표 animal = [list(map(int, sys.stdin.readline().split())) for i in range(N)] saro.sort() count = 0 for a, b in animal: if b > L: # 동물 좌표 b가 L보다 크면 잡을수없다. continue start = 0..
