대학원생이 쉽게 설명해보기

# A 행렬을 선언합니다.
N, A_M = map(int, input().split())
A = []
for _ in range(N):
    A.append(list(map(int, input().split())))
    
# B 행렬을 선언합니다.
B_M, K = map(int, input().split())
B = []
for _ in range(B_M):
    B.append(list(map(int, input().split())))
    
result = []

# A에서 각 row에 해당하는 list를 가져옵니다.
for A_subset in A:
    # A_subset row의 n 번째 원소는 B의 n 번째 col과 곱해집니다.
    # 곱한 후, 더해주면 결과 행렬의 n 번째 row가 만들어집니다.
    # 이를 위해 열 갯수만큼의 B_subset을 만듭니다.
    B_subset = [0] * K
    # A_subset의 col 갯수만큼 for-loop가 반복됩니다.
    for i, ele in enumerate(A_subset):
        # A_subset row의 i 번째 숫자와 B의 i 번째 행에 해당하는 수를 곱합니다.
        # 숫자와 행을 바로 곱하는 작업은 선형 조합(맞나?)를 생각해보면 쉽습니다.
        target_subset = [ele * num for num in B[i]]
        # B_subset에 전부 더해주면 끝
        B_subset = [sum(x) for x in zip(B_subset, target_subset)]
    result.append(B_subset)
    
for row in result:
    print(*row)

이 문제는 행렬곱만 알고 있다면, 3중 for-loop로 쉽게 해결할 수 있다.

# 거듭제곱을 빠르게 구하는 방법은 
# 백준 1629번을 참고하세요.
def solve(A, B):
    if(B % 2 > 0):
        return solve(A, B - 1) * A
    elif(B == 0):
        return 1
    elif(B == 1):
        return A
    else:
        result = solve(A, B//2)
        return result ** 2 % p

N, K = map(int, input().split())    

n_part = 1
nk_part = 1

p =  1000000007

# N! 부분
for num in range(1, N+1):
    n_part *= num; n_part %= p

# K! 부분
for num in range(1, K+1):
    nk_part *= num; nk_part %= p

# (N-K)! 부분
for num in range(1, N-K+1):
    nk_part *= num; nk_part %= p
    
# (p-2) 제곱 부분은 거듭제곱을 빠르게 구하는 방법을
# 그대로 가져와서 사용합니다.
nk_part = solve(nk_part, p-2) % p

result = (n_part * nk_part) % p
print(result)

페르마의 정리를 처음 접해봤는데, 무엇보다 이항계수가 페르마의 정리에 의해 어떻게 단순화될 수 있는지 직접 손으로 풀어보면 바로 코드로 옮길 수 있을 것이다.

페르마의 정리를 통해 이항계수의 분모에 해당하는 K!(N-K)!를 거듭제곱 형태로 바꿔주어 시간복잡도를 줄일 수 있다.

A, B, C = map(int, input().split())

def solve(A, B):
    if(B % 2 > 0):
        return solve(A, B - 1) * A
    elif(B == 0):
        return 1
    elif(B == 1):
        return A
    else:
        # 10^11에서 11을 %2 해줄때의 경우는 홀수와 짝수로 나뉘게 된다.
        # 첫 시작부터 % 12를 붙이고 끝까지 계산을 해보면,
        # 왜 result ** 2 % C가 필요한지 알 수 있다.
        result = solve(A, B//2)
        return result ** 2 % C

# 식을 보는 도중, 여기서 왜 또 %C를 해주는지 헷갈릴 수 있는데,
# solve(A, B)는 (10, 11)의 결괏값이고,
# (10, 11) % C는 문제가 원하는 정답이다.
print(solve(A, B) % C)

result ** 2 % C를 찾느라고 시간이 좀 더 걸렸다.
(10^10%12는 10^5^2%12와 같다.)

이 문제는 코드 길이에 비해 정답률이 낮길래 구글에 검색을 좀 해보았는데, 생각보다 풀이가 다양했다.

문제를 풀고 검색을 통해 다른 방법도 접해보길 바란다.

N = int(input())

paper = [list(map(int, input().split())) for _ in range(N)]

neg = 0
neut = 0
pos = 0

def clip_paper(x, y, n):
    global neg, neut, pos
    
    num_check = paper[x][y]
    for i in range(x, x + n):
        for j in range(y, y + n):
            if(paper[i][j] != num_check):
                for k in range(3):
                    for l in range(3):
                        clip_paper(x + k * n//3, y + l * n//3, n//3)
                return
            
    if(num_check == -1):
        neg += 1
    elif(num_check == 0):
        neut += 1
    else:
        pos += 1
        
clip_paper(0, 0, N)
print(f'{neg}\n{neut}\n{pos}')

N = int(input())

image = [list(map(int, input())) for _ in range(N)]

def quadtree(x, y, n):
    # n = 1, 하나의 픽셀만 볼 경우,
    if(n == 1):
        return str(image[x][y])
    
    result = []
    for i in range(x, x + n):
        for j in range(y, y + n):
            # 색이 다르면, 다시 분할하자.
            if(image[i][j] != image[x][y]):
                # append와 extend의 차이는
                # extend는 list, tuple, dict 등의 iterable object를
                # python list의 끝에 append 해주는 것.
                result.append('(')
                result.extend(quadtree(x, y, n//2))
                result.extend(quadtree(x, y + n//2, n//2))
                result.extend(quadtree(x + n//2, y, n//2))
                result.extend(quadtree(x + n//2, y + n//2, n//2))
                result.append(')')
                
                return result
            
    return str(image[x][y])
    
print(''.join(quadtree(0, 0, N)))