문제 가장 긴 증가하는 부분 수열 4 풀이 핵심 긴 수열 길이 구하기 순서 바꾸기로 가능 긴 수열 구하기 순서 바뀌어 다시 구해줘야함. 실패 순서가 바뀌는 걸 이해하지 못함. 외워서 풀었다는 이야기 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from bisect import bisect_left n = int(input()) arr = list(map(int, input()....
문제 가장 긴 증가하는 부분 수열 풀이 핵심 정렬된 수열 back < new => append back > new => bisect_left(arr, new + 1) 구체적인 로직 bisect_left n개 int로 받기 arr 받기 arr sort longest_arr = [0] for i in arr: back < i => append back > i => arr[bisect_left(arr, i + 1)] = i print(len(longest_arr) - 1) 실패 기억에 따라 증가하기만 해야한다고 생각해 같은값을 대체했다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 from bisect import bisect_left n = int(input()) arr= list(map(int, input()....
문제 이동하기 풀이 핵심 dp[i][j] => i,j에서 먹을 수 있는 최대 값 dp[i][j] = max(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + arr[i][j] 구체적인 풀이 n,m 받기 arr로 int전환해서 map받기 for i in n for j in m dp ~ print(dp[n - 1][m - 1]) 코드 1 2 3 4 5 6 7 8 9 10 11 12 n,m = list(map(int, input().split())) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n+ 1): for j in range(1, m+1): dp[i][j] = max(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + arr[i-1][j-1] print(dp[n][m])
문제 이친수 풀이 핵심 dp[i][k] => i 자리 끝이 k인 이친수 dp[i][0] = dp[i-1][1] + dp[i -1][0] dp[i][1] = dp[i-1][0] dp[1][0] = 0 dp[1][1] = 1 구체적인 코드 n받는다. dp n, 2짜리 2차원 arr만든다 dp[1][0] = 0, dp[1][1] = 1 for i in 2 ~ n: dp[i][0] = dp[i-1][1] + dp[i-1][0] dp[i][1] = dp[i-1][0] print(dp[n][0] + dp[n][1]) 코드 1 2 3 4 5 6 7 8 9 10 11 n = int(input()) dp = [[0] * 2 for _ in range(n + 1)] dp[1][0] = 0 dp[1][1] = 1 for i in range(2, n + 1): dp[i][0] = dp[i-1][0] + dp[i-1][1] dp[i][1] = dp[i-1][0] print(dp[n][0] + dp[n][1])
문제 동전2 풀이 핵심 종류로 DP를 만든다. DP[K]는 K를 만들 수 있는 최소 동전 개수다. 구체적인 로직 n,k 받기 arr에 array 받기 for i ~ n dp[i][k] = min(dp[i-1][k], dp[k - arr[i]], k % i == 0 ? k / i : INF) print dp[n][k] 주의 문제를 제대로 읽지 않아서 구할 수 없는 경우를 처리하지 못했다. 코드로 옮기기 전에 조건을 다시한번 확인하자. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 n,k = list(map(int, input()....