전체 글

문제 (링크) https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 나의 풀이 import sys from itertools import combinations input = sys.stdin.readline n, s = map(int, input().split()) arr = list(map(int, input().split())) # meet in the middle arr_1 = arr[:n//2] arr..

문제 (링크) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n, k = map(int, input().split()) items = [] for _ in range(n): items.append(list(map(int, input().split()))) # dp[i][j] -> 최대 무게가 j일 때..

문제 (링크) https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 나의 풀이 이 문제는 투포인터와 이진탐색을 모두 사용할 수 있다. 1) 투포인터 사용 import sys input = sys.stdin.readline n = int(input()) liquids = list(map(int, input().split())) left_idx = 0 right_idx = n - 1 ans = abs(liquids[left_idx] + liquid..

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

문제 (링크) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 나의 풀이 import sys from itertools import combinations input = sys.stdin.readline n, s = map(int, input().split()) arr = list(map(int, input().split())) cnt = 0 for i in range(1, n+1): comb = combin..

문제 (링크) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n, c = map(int, input().split()) arr = [] for _ in range(n): arr.append(int(input())) arr.sort() end = arr[-1] - arr[0] start = 1 ans = 0 whil..

문제 (링크) https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline seq_1 = input().rstrip() seq_2 = input().rstrip() seq_3 = input().rstrip() x = len(seq_1) y = len(seq_2) z = len(seq_3) arr = [[[0] * (z+1) for _ in range(y+1)] for _ in range(x+1..

문제 (링크) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline seq_1 = input().rstrip() seq_2 = input().rstrip() n = len(seq_1) m = len(seq_2) arr = [[0] * (n+1) for _ in range(m+1)] for i in range(1, m+1): ..