📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net ❓ 문제 ❗ 풀이 분할 정복(재귀 함수) 사용 📗 풀이 코드 import sys input = sys.stdin.readline def mul_func(a1,a2): # 행렬 곱 연산 함수 mul = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): a1_row = a1[i] for j in range(n)..
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/2740 ❓ 문제 ❗ 풀이 행렬 전환하여 행렬 곱 연산 진행 📗 풀이 코드 import sys input = sys.stdin.readline n,m = map(int,input().split()) list_a = [list(map(int,input().split())) for _ in range(n)] _,k = map(int,input().split()) # 행렬 곱셈이 가능하려면 a의 열과 b의 행이 같아야하기에 m 생략 list_b = [[] for _ in range(k)] for _ in range(m): for i,num in enumerate(map(int,input().split()))..
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net ❓ 문제 ❗ 풀이 (a**n)%c == (((a**(n-1))%c)*a)%c라는 성질 이용 📗 풀이 코드 import sys input = sys.stdin.readline a,b,c = map(int,input().split()) rests = [] # a**i의 나머지 집합 i = 1 rests.append(a%c) # rests에는 a**1의 나머지, a**2의 나머지, a**4의 나머지, a**8의 나머지....
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net ❓ 문제 ❗ 풀이 재귀함수 활용 📗 풀이 코드 import sys input = sys.stdin.readline # 2차원 배열이 모두 같은 수인지 확인하고 아니면 4등분하는 함수 def division(n, sum_video, video): global ans if not sum_video%n**2 : # 모두 같은 수라면 나머지가 0..
📌문제 출처 백준 단계별 문제풀이 - 분할정복 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ❓ 문제 ❗ 풀이 재귀함수 활용 📗 풀이 코드 import sys input = sys.stdin.readline # n*n 행렬에서 전체가 다 같은 색인지 확인 후 아니면 4등분하는 함수 def division(n,paper,sum_paper): # 모두 같은 색인 경우 if not sum_paper%(n**2) : # 전..
📌문제 출처 백준 단계별 문제풀이 - 그리디 알고리즘 https://www.acmicpc.net/problem/13305 ❓ 문제 ❗ 풀이 그리디 알고리즘 활용 📗 풀이 코드 import sys input = sys.stdin.readline n = int(input()) # 시작할 때 주유하고, 기름을 넣은 주유소보다 기름값이 싼 주유소를 만나면 거기서 주유한다. roads = list(map(int,input().split())) costs = list(map(int,input().split()))[:-1] # 도착지점에서는 기름을 안넣으니 제외 tot_cost = 0 # 최종 전체 주유비 tmp_cost = costs[0] # 주유할 주유소에서의 비용, 첫번째 주유소에서 주유 후 시작 tmp_roa..
📌문제 출처 백준 단계별 문제풀이 - 그리디 알고리즘 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net ❓ 문제 ❗ 풀이 - 빼주는 수를 가장 크게 만든다. 📗 풀이 코드 import sys input = sys.stdin.readline # eval 함수 사용 num_op = ['('] # 문자열을 하나의 수나 연산자로 만들어 넣어줄 리스트 num = '' for s in input().strip(): if s not in ['+','-'..
📌문제 출처 백준 단계별 문제풀이 - 그리디 알고리즘 https://www.acmicpc.net/problem/11399 ❓ 문제 ❗ 풀이 정렬 후 누적합 📗 풀이 코드 import sys input = sys.stdin.readline n = int(input()) # 빨리 인출하는 사람이 먼저 뽑고 나가야 뒤에서 덜 기다림 times = sorted(list(map(int,input().split()))) # 시간 순으로 정렬 waiting = [] # 재정렬한 순서대로 뽑았을 때 순서별 대기시간 tmp_time = 0 # 현재 사람의 대기시간 # 누적합 구하기 for time in times : tmp_time += time waiting.append(tmp_time) print(sum(waitin..
