sm 기술 블로그

import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] A = br.readLine().split(""); String[] B = br.readLine().split(""); int LengthA = A.length + 1; int LengthB = B.length + 1; int[][] arr = new int[LengthA][LengthB]; for (int i = 1; i < LengthA; i++) { for ..

import sys input = sys.stdin.readline A = input().strip() B = input().strip() lenA = len(A)+1 lenB = len(B)+1 arr = [[0]*(lenB) for _ in range(lenA)] for i in range(1,lenA): for j in range(1,lenB): if A[i-1] == B[j-1]: arr[i][j] = arr[i-1][j-1] + 1 else: arr[i][j] = max(arr[i-1][j], arr[i][j-1]) print(arr[-1][-1]) 문제요약 첫번째 문자열과 두번째 문자열의 부분 수열이 되는 것 중 가장 긴 것을 찾아라. 설명 일치하는 문자를 구하라는 문제가 아니라 부분 수열이 ..

import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[][] Eline = new int[N][N]; int[] DP = new int[N]; for (int i = 0; i < N; i++) { String[] tmp = br.readLine().split(" "); Eline[i][0] = Integer.parseInt(tmp[0]); Eline[i..

import sys input = sys.stdin.readline N = int(input()) Eline = sorted([list(map(int,input().split())) for _ in range(N)]) DP = [1 for _ in range(N)] for i in range(N): for j in range(i): if Eline[i][1] > Eline[j][1]: DP[i] = max(DP[i], DP[j]+1) print(N-max(DP)) 문제요약 서로 교차되지 않게 할때 제거 할 전깃줄 최소 개수 설명 LIS (최장증가수열) 를 이용하면 된다. DP는 설치 가능한 갯수를 뜻한다. 따라서 총 전깃줄 - 서로 교차되지 않는 최대의 를 해주면 제거해야할 최소의 전깃줄 개수가 나오게 ..