💻 준성 개발 일지

문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 # 백준 2225번 문제 - 합분해 import sys input = sys.stdin.readline n, k = map(int, input().split()) dp = [[0]*201 for _ in range(201)] for j in range(201): dp[1][j] = 1 dp[2][j] = j + 1 for i in range(2, 201): dp[i][1] = i for j in range(2, 201): dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000000 p..

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 # 백준 1916번 문제 - 최소비용 구하기 import sys import heapq input = sys.stdin.readline n, m= int(input()), int(input()) graph = [[] for _ in range(n+1)] INF = 1e9 distance = [INF] * (n+1) for _ in range(m): a,..

문제 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 # 백준 5582번 문제 - 공통 부분 문자열 answer = 0 str1, str2 = input(), input() dp=[[0] * (len(str2) + 1) for _ in range(len(str1) + 1)] for i in range(1, len(str1)+1): for j in range(1, len(str2)+1): if (str1[i-1] == str2[j..

문제 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 # 백준 6588번 문제 - 골드바흐의 추측 import sys input = sys.stdin.readline n = 1000001 # 소수 아닌 모든 홀수 처리 prime = [1] * n for i in range(3, int(n ** 0.5) + 1, 2): if prime[i]: for j in range(i * 2, n, i): prime[j] = 0 ..

문제 https://www.acmicpc.net/problem/2042 풀이 # 백준 2042번 문제 - 구간 합 구하기 # 0. 입력받기 import sys input = sys.stdin.readline n, m, k = map(int,input().split()) arr = [] segment_tree = [0]*(n*4) # 1. 트리 만들기 def init(start, end, index): # start와 end가 같다면 리프노드이다. if start == end: segment_tree[index] = arr[start-1] return segment_tree[index] # 현재 노드는 왼쪽 아래 노드와 오른쪽 아래 노드를 더한 값이다. mid = (start+end) // 2 segmen..

문제 https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 풀이 # 백준 11478번 문제 - 서로 다른 부분 문자열의 개수 string = input() stack = set() for i in range(len(string)): for j in range(i, len(string)): stack.add(string[i:j+1]) print(len(stack))

문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 풀이 # 백준 2512번 문제 - 예산 n = int(input()) money = list(map(int, input().split())) budget = int(input()) start, end = 0, max(money) def binary(money): start = 0 end = max(money) while start = mid: cnt += mid else: cnt += ..

문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 # 백준 1107번 문제 - 리모컨 import sys input = sys.stdin.readline target = int(input()) n = int(input()) broken = list(map(int, input().split())) # 현재 채널에서 + 혹은 -만 사용하여 이동하는 경우 cnt = abs(100 - target) for nums in ran..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 # 백준 9251번 문제 - LCS str1 = ' ' + input() str2 = ' ' + input() dp = [[0]*len(str1) for _ in range(len(str2))] for i in range(1, len(str2)): for j in range(1, len(str1)): if str2[i] == str1[j]: ..

문제 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 # 백준 1011번 문제 - Fly me to the Alpha Centauri t = int(input()) for _ in range(t): x, y = map(int, input().split()) distance = y - x cnt = 0 move = 1 move_plus = 0 # 이동한 거리의 합 while move_plus < ..