접근 1. dp를 이용하여 dp[i]를 길이가 i일때 i번째 수로 만들 수 있는 증가하는 부분 수열의 길이로 둔다. dp[i+1]를 구하기 위해 i+1보다 더 작은 수들을 찾는다. 이 수들 중 dp의 값이 가장 큰 수를 j라고 한다면 dp[j]+1 이 dp[i+1] 이 된다. 2. 직접 가장 긴 증가하는 부분 수열을 만든다. 10 12 20 8 9 10 15 30 50 이라는 수열이 있다고 생각해보자. arr = [0] 를 두고 arr[-1] 보다 크면 추가, 작으면 기존 수와 교체하여 구한다. arr = [0 10 12 20] 이면 다음 수가 8이다. 이때 기존수 10과 교체한다. 이 문제는 부분 수열의 길이를 구하는 문제이기 때문에 중간에 끝나더라도 길이 자체는 그대로 출력되게 된다. 나의 코드(직접..

접근 일단 LCS가 어떤건지 기억이 안나 관찰하면서 감을 잡았다. ACAYK와 CAPCAK에 대한 LCS로 ACAK라고 한다. 두문자열이 있을때 첫번째 문자의 1,2,3,5 인덱스에서 ACAK를 찾을 수 있고 2,4,5,6 인덱스에서 ACAK를 찾을 수 있다. 그리고 2개의 문자열을 놓고 각 자리까지의 LCS를 직접구해보았다. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 A 1 2 3 3 3 3 K 1 2 3 3 4 4 이렇게 직접 구했는데 점화식을 알기가 너무 어려웠다. 같을 때 1이 올라가고 다를때는 옆과 밑에서 값을 가져오면 된다는건 직접 구하면서 느꼈는데 코딩으로 옮길때 1행과 1열쪽이 어떻게 구해야하는지 감이 오지않았다..

접근 최대값을 구하는 문제. 배열을 만들어서 dp[i][j]일때의 최대값을 dp[i][j]에 저장하자. dp[i-1][j-1], dp[i-1][j]가 각각 해당자리의 최대값이라면 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + cost[i][j] 가 된다. 해당 점화식을 보면 dp[i][j]를 구하기위해 dp[i-1] 만 필요하니 dp테이블을 모두 만드는것이아닌 1차원 2개만 만들면 메모리를 아낄 수 있다. 속도적인 측면에서는 그냥 배열을 쓰는게 좋겠지만 메모리를 절약하기 위해 1차원 배열 2개만을 이용해서 구현할 생각을 했다. 나의 코드 import sys input = sys.stdin.readline n = int(input()) dp = list(map(int,inpu..

접근 브루트포스로 모든 경우 탐색을 해서 최소 비용을 알아내야겠다. dfs로 탐색해서 최소값을 업데이트하고 최소값을 비교해가면서 최소값보다 합이 커지면 처음 단계로 돌아가야겠다. 나의 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) n = int(input()) M = [list(map(int,input().split())) for _ in range(n)] minvalue = sys.maxsize def dfs(cnt,value,p): global minvalue if value >= minvalue: return if cnt == n: minvalue = min(value,minvalue) else: for i in rang..