문제http://boj.ma/31671 31671번: 특별한 오름 등반 boj.ma 풀이문제 요약출발점에서 도착점까지 주어진 규칙대로 이동하면서, 최대한 높게 도달할 수 있는 y를 구하자.아이디어출발점과 도착점으로부터 선생님을 피하며, 모든 가능한 영역을 가보자. 이후 두 탐색에 대한 교차점 중 y가 가장 높은 경우를 찾으면 된다.점화식은 다음과 같다.dp[D][x][y] : D(출발점 또는 도착점)에서 출발했을 때 (x, y)에 도달할 수 있는지 여부 // Solve boolean[][][] dp = new boolean[2][WIDTH][HEIGHT]; int[] D = new int[] {-1, 1}; dp[L][0][0] = true; ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-the-sum-of-the-subsequences-is-m/description 부분 수열의 합이 M 설명 | 코드트리부분 수열의 합이 M를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약수열 A의 부분 수열 중 합이 M이 되는 경우 중 가장 짧은 길이를 구하자.아이디어0-1 냅색 문제이다. 점화식은 다음과 같다.dp[i] : 합이 i가 되는 부분 수열의 최소 길이동일한 원소를 여러 번 사용하는 것을 방지하기 위해 각 원소에 대해 역순으로 탐색하자.n, m = map(int, input().sp..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-coin-change/description 동전 거슬러주기 설명 | 코드트리동전 거슬러주기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약종류 N개의 동전을 최소로 사용해 M원을 만들자아이디어N, M = map(int, input().split())coin = list(map(int, input().split()))# Please write your code here.INF = int(1e10)dp = [INF] * (M + 1)dp[0] = 0for i in range(1, M + 1): ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/test-being-rich-by-working-part-time/description 알바로 부자 되기 설명 | 코드트리알바로 부자 되기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약여러개의 알바 시작/종료 시간과 임금이 주어졌을 때, 최대한 많은 돈을 벌어보자.아이디어다른 알바가 끝나야. 새로운 알바를 할 수 있다. 입력받은 알바 정보에 대해 종료시간을 기준으로 정렬해주자.점화식은 다음과 같다.dp[i] : i번째 알바를 마지막으로 선택했을 때의 최대 이익n = int(input())jobs = [..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-increasing-and-descreasing-subsequence/description 증가했다가 감소하는 부분 수열 설명 | 코드트리증가했다가 감소하는 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약가장 긴 LIS + LDS를 구하자.아이디어LIS와 LDS를 동시에 구해주자.점화식은 다음과 같다.dp[state][i] : i번째 요소로 끝나는 LIS 또는 LDS의 최대 길이LIS, LDS를 비교하며 최댓값을 LDS에 기록해 하나의 부분 수열에 대한 최대 길이로 계산하자...

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-select-segments-without-overlap-2/description 겹치지 않게 선분 고르기 2 설명 | 코드트리겹치지 않게 선분 고르기 2를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약수직선 상의 N개의 선분을 겹치지 않도록 최대한 많은 선분을 선택하자.아이디어우선 주어진 선분이 정렬되어있다는 보장이 없다.정렬을 한 후 임의의 선분에 대해 이전 선분을 선택했을 때보다 더 많은 선분을 선택할 수 있는지 확인해야 한다.점화식은 다음과 같다.dp[i] : i번째 선분의 끝 ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-longest-increasing-sequence-2d/description 2차원 최대 증가 수열 설명 | 코드트리2차원 최대 증가 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N * N 행렬에서 (1, 1)에서 오른쪽 아래 어느 범위로든 현재 칸보다 더 큰 숫자로 최대한 많이 점프하자.아이디어N, M이 50으로 작아 모든 현재 위치에 대해 모든 이전 위치로부터 최대 점프 횟수를 구할 수 있다.점화식은 다음과 같다.dp[i][j] : (i, j)에 도착했을 때 지금까지 ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-maximum-number-of-jumps/description 풀이문제 요약각 요소의 수 arr[i]에 대해 1 ~ arr[i] 만큼 앞으로 건너뛸 수 있을 때 최대한 많이 점프하는 횟수를 구하자.아이디어점화식은 다음과 같다.dp[i] : i번째 요소에서 1 ~ arr[i] 만큼 점프해서 갈 수 있는 최대 점프 횟수주어진 배열의 반대부터 계산하면 쉽게 해결할 수 있다.만약 arr[i]이 0보다 크면 1칸 이상 점프가 가능하다.i + 1 부터 min(i + arr[i] + 1, n - 1)까지 점프 할 수 있으므로 이 중 최댓값을 찾아서 점프해주며 dp[0]까지 진행하자.n = i..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-longest-decreasing-subsequence/description 최대 감소 부분 수열 설명 | 코드트리최대 감소 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 수열에서 가장 긴 감소하는 부분 수열의 길이를 구하자.아이디어점화식은 다음과 같다.dp[i] : i번째 요소로 끝나는 LDS의 최대 길이LIS의 응용문제다. 부등호만 바꾸면 된다.n = int(input())m = list(map(int, input().split()))# Please write yo..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-longest-increasing-subsequence/description풀이문제 요약주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하자.아이디어LIS를 구하는 가장 기본적인 문제다.점화식은 다음과 같다.dp[i] : i번째 요소로 끝나는 LIS의 최대 길이현재 위치 i에 대해 이전 위치 0 ~ i - 1 중 현재 위치의 값 m[i]]보다 작고, 지금까지 구한 LIS보다 dp[j] + 1이 더 긴 LIS가 된다면 다음이 성립한다.dp[i] = max(dp[i], dp[j] + 1)n = int(input())m = list(map(int, input().split()))# Ple..