문제링크: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..
문제링크:https://www.acmicpc.net/problem/2470 import sys N = int(sys.stdin.readline()) Liquid = list(map(int, sys.stdin.readline().split())) Liquid.sort() start = 0 end = len(Liquid) - 1 mix = sys.maxsize # 최솟값 변수 초기화 while start < end: newmix = Liquid[start] + Liquid[end] if abs(newmix) < mix: # 기존의 mix값보다 new mix의 절대값이 작을떄 mix = abs(newmix) ans = [Liquid[start], Liquid[end]] if newmix < 0: # 0보다 작..
문제링크:https://www.acmicpc.net/problem/2110 import sys N, C = map(int, sys.stdin.readline().split()) home = [] for _ in range(N): home.append(int(sys.stdin.readline())) home.sort() # 이분 탐색을 위해 정렬 start = 0 end = home[-1] ans = 0 def binary(arr, s, e): while s = current + m: # arr[i]보다 작거나 같으면 count +=1 공유기를 arr[i]에 설치 count += 1 current = arr[i] if count >= C: # C를 넘어가면 더 넓게 설치할수있다는 말 => s = m+1 g..
문제링크:https://www.acmicpc.net/problem/10971 import sys input = sys.stdin.readline n = int(input()) costs = [list(map(int, input().split())) for _ in range(n)] visited = [0] * n # 방문했는지 안했는지 sum_cost = 0 # 방문비용 합 ans = sys.maxsize def dfs(depth, x): global sum_cost, ans if depth == n - 1: # 종료 조건 if costs[x][0]: sum_cost += costs[x][0] if sum_cost < ans: # 최소값 비교 ans = sum_cost sum_cost -= costs[x..
