eaz_coding

문제https://www.acmicpc.net/problem/11660 풀이import sysinput = sys.stdin.readlinen, m = map(int, input().split())arr = [list(map(int, input().split())) for _ in range(n)]dp = [[0 for _ in range(n+1)] for _ in range(n+1)]for i in range(1, n+1): for j in range(1, n+1): dp[i][j] = arr[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]for _ in range(m): x1, y1, x2, y2 = map(int, input().sp..

문제https://www.acmicpc.net/problem/1167 풀이지난번에 풀었던 1967번 트리의 지름을 그대로 이용한 문제 풀이다.트리의 지름은 하나의 공식처럼 이해하면 좋을 것 같다.    1. 루트 노드에서 각 노드까지 최소 거리를 구한다.    2. 최소 거리가 가장 먼 노드에서 가장 먼 거리를 구한다.import sysinput = sys.stdin.readlinefrom collections import dequev = int(input())nodes = [[] for _ in range(v+1)]for _ in range(v): q = deque(list(map(int, input().split()))) x = q.popleft() while q: y =..

문제https://www.acmicpc.net/problem/9019 풀이오답에서 놓쳤던 부분들1. L과 R에서 이동할때, str로 변경하지 않고 몫과 나머지로 계산해서 구할 수 있다.2. visited를 딕셔너리로 하는 것보다 리스트로 만들어서 인덱싱 하는 것이 더 빠르다.3. visited를 통해 더 적은 수로 미리 만들어진 곳은 큐에 추가하지 않는다. import sysinput = sys.stdin.readlinefrom collections import dequet = int(input())for _ in range(t): visited = [False for _ in range(10001)] a, b = map(int, input().split()) q = deque() q.appe..

문제https://www.acmicpc.net/problem/17144  풀이import sysinput = sys.stdin.readliner, c, time = map(int, input().split())arr = []purifier = []for i in range(r): arr.append(list(map(int, input().split()))) for j in range(c): if arr[i][j] == -1: purifier.append((i, j))directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]opposite = [(0, 1), (-1, 0), (0, -1), (1, 0)]def area(x, y): ..

문제https://www.acmicpc.net/problem/14891 풀이import sysinput = sys.stdin.readlinewheel = [list(input().strip()) for _ in range(4)]k = int(input())def check(now, i, directions): if i == 2: if now 0 and wheel[now][i] != wheel[now-1][2]: directions[now-1] = -directions[now] directions = check(now-1, i, directions) return directionsdef move(before, direction): res..

문제세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.배열 A와 B의 인덱스는 1부터 시작한다. https://www.acmicpc.net/problem/1300 풀이import sysinput = sys.stdin.readlinen = int(input())k = int(input())s, e = 1, kanswer = 0while s = k: answer = m e = m-1 else: s = m+1print(answer)

문제요약1 한개 타일과 00 두개 타일이 있을 때, n개의 타일로 만들 수 있는 이진수의 개수를 15746으로 나눈 나머지를 구하시오. 원본https://www.acmicpc.net/problem/1904  풀이import sysinput = sys.stdin.readlinen = int(input())lst = [0, 1, 2]if n > 2: for i in range(3, n+1): lst.append((lst[i-1]+lst[i-2]) % 15746)print(lst[n])

문제https://www.acmicpc.net/problem/2805 풀이from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())trees = list(map(int, input().split()))u, l = max(trees), 1answer = 0while l 0: s += (trees[i] - mid) if s >= m: break if s >= m: if answer

풀이import sysinput = sys.stdin.readlinen, k = map(int, input().split())items = [tuple(map(int, input().split())) for _ in range(n)]dp = [[0] * (k+1) for _ in range(n+1)]for i in range(1, n+1): for j in range(1, k+1): if j >= items[i-1][0]: dp[i][j] = max(items[i-1][1]+dp[i-1][j-items[i-1][0]], dp[i-1][j]) else: dp[i][j] = dp[i-1][j]print(dp[n][k])

문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 원본https://www.acmicpc.net/problem/9251 풀이import sysinput = sys.stdin.readlinea = list(input())b = list(input())arr = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]for i in range(1, len(a)+1): for j in range(1, len(b)+1): if a[i-1] == b[j-1]: ..