본문 바로가기
반응형

Problem Solving/BOJ225

[BOJ][Python]10830 풀이 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net def matmul(mat1, mat2): result = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): for j in range(n): for k in range(n): result[i][j] += mat1[i][k] * mat2[k][j] result[i][j] %= 1000 return result n, b = map(int, input()... 2023. 8. 28.
[BOJ][Python]9935 풀이 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net s = input() e = input() stack = [] for char in s: stack.append(char) if char == e[-1]: if ''.join(stack[-len(e):]) == e: for _ in range(len(e)): stack.pop() ans = ''.join(stack) print(ans if ans != '' else 'FRULA') .. 2023. 8. 27.
[BOJ][Python]5639 풀이 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net import sys ssr = sys.stdin.readline sys.setrecursionlimit(100000) def make_tree(): first_key = int(ssr()) tree = {first_key:[0, 0]} while True: try: cur_key = int(ssr()) tree[cur_key] = [0, 0] parent_key = first_key .. 2023. 8. 26.
[BOJ][Python]2638 풀이 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline def outer_air(): nomis = [] while q: r, c = q.popleft() for dr, dc in dpos: if 0 1: nomis.append((r, c)) q.append((r, c)) for r, c in nomis: board[r][.. 2023. 8. 24.
[BOJ][Python]2448 풀이 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net def recur(n): if n == 3: return [' * ', ' * * ', '*****'] else: half = n//2 before = recur(half) result = ['' for _ in range(n)] for i in range(half): result[i] = ' '*(half) + before[i] + ' '*(half) for i in range(half, n): result[i] = before[i-half] + .. 2023. 8. 23.
[BOJ][Python]2096 풀이 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net import sys ssr = sys.stdin.readline def max_dp(): scores = [board[0][0], board[0][1], board[0][2]] dpos = (-1, 0, 1) for r in range(n): if r == n-1: break tmps = [i for i in scores] scores = [tmps[i]+board[r+1][i] for i in range(3).. 2023. 8. 22.
[BOJ][Python]1987 풀이 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net import sys ssr = sys.stdin.readline def dfs_stack(): global ans s = [(0, 0, board[0][0])] while s: r, c, path = s.pop() if len(path) > ans: ans = len(path) if len(path) == 26: break for dr, dc, in dpos: if 0 2023. 8. 21.
[BOJ][Python]11444 풀이 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net def matrix_multiplication(matrix1, matrix2): result = [[0, 0], [0, 0]] for i in range(2): for j in range(2): for k in range(2): result[i][j] += matrix1[i][k]*matrix2[k][j] result[i][j] %= 1000000007 return result n = int(input()) ans = [[1, 0], [0, 1]] fib_mat = [[1,.. 2023. 8. 19.
[BOJ][Python]11404 풀이 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import sys ssr = sys.stdin.readline INF = 10000001 n = int(ssr()) m = int(ssr()) min_cost = [[INF for _ in range(n)] for _ in range(n)] for _ in range(m): a, b, c = map(int, ssr().split()) min_cost[a-1][b-1] = min(min_cost[.. 2023. 8. 11.
[BOJ][Python]2206 풀이 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline INF = 1000001 def bfs(): dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)] visited = [[0 for _ in range(m)] for _ in range(n)] visited[0][0] = 1 q = de.. 2023. 8. 9.
반응형

티스토리툴바