DP

실버 3 DPhttps://www.acmicpc.net/problem/1463DP 문제를 풀 땐 3가지 단계를 생각한다.1\. 테이블 정의 2\. 점화식 찾기3\. 초기값 정하기 문제에 적용해보자.테이블 정의Di = 정수가 i를 1로 만들때 연산을 하는 횟수의

실버 3 https://www.acmicpc.net/problem/11726DP 문제푸는 방법 1\. 테이블 정의2\. 점화식 찾기3\. 초기값 정하기 테이블 정의 Di = 2xi 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수 점화식 찾기 직사각형

실버 3 https://www.acmicpc.net/problem/1172711726번 2xn 타일링 문제와 비슷하지만 2x2 타일이 추가되었다. 테이블 정의하기 Di = 2xi 크기의 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수점화식 찾기 D

실버 3 https://www.acmicpc.net/problem/9095테이블 정의하기Di = i를 1,2,3의 합으로 나타내는 방법의 수 점화식 찾기정수 4일 때 1+1+1+1, 1+2+1, 2+1+1, 3+1 -> 3을 1,2,3의 합으로 나타내는 방법

실버 1 https://www.acmicpc.net/problem/11052(자세한 문제는 링크 클릭)테이블 정의Di = 카드가 i개일 때 지불해야하는 최대 금액 점화식 찾기 카드가 1개 들어있는 카드팩을 구매하고 카드 i-1개를 구입한다. 카드가 2개 들어있

실버 1 https://www.acmicpc.net/problem/1619411052번 문제와 비슷하지만 이 문제는 최댓값이 아닌 최솟값을 구하는 문제이다. 점화식도 비슷하지만 max -> min 으로 바꿔주면 되고 DP의 초기값을 integer의 max va

실버 2 https://www.acmicpc.net/problem/15990이 문제는 9095번 1,2,3 더하기와 비슷하지만 조건이 하나 추가되었습니다. 같은 수를 두 번 이상 연속해서 사용하면 안된다는 조건입니다. 이 점을 고려하여 문제를 풀어보겠습니다.

실버 1 https://www.acmicpc.net/problem/10844테이블 정의하기dpi = 길이가 i이고, j로 시작하는 수들 중 계단 수의 개수 점화식 찾기길이가 1일 때 계단수는 9개입니다. 길이가 2일 때 생각해봅시다. 첫째 자리가 0과 9일 때

실버 3 https://www.acmicpc.net/problem/2193테이블 정의하기dpi j로 끝나는 i자리 이친수의 개수 점화식 세우기 j=0 일 때, dp3 = dp2 + dp2j=1 일 때, dp3 = dp2초기값 정하기 dp1 = 0dp1 = 1

실버 2 https://www.acmicpc.net/problem/11053LIS(Longest Increasing Subsequence)의 길이를 구하는 문제입니다. 테이블 정의하기dpi = i번째 수열일 때 가장 긴 증가하는 부분 수열의 길이 점화식 세우기

골드 4 https://www.acmicpc.net/problem/14002!11053번 가장 긴 증가하는 부불 수열과 비슷한 문제입니다. 11053번과 길이를 구하는 건 동일하되 가장 긴 증가하는 부분 수열을 출력해야합니다. dp 배열에 저장되어있는 값으로

실버 2 https://www.acmicpc.net/problem/1912배열을 반복문으로 돌며 합을 구하되 합과 max 값을 비교하며 max값을 업데이트합니다.합이 음수일 땐 합을 0으로 초기화해주는 작업을 합니다.

실버 3 https://www.acmicpc.net/problem/1699테이블 정의하기dpi = 제곱수 합의 최소 개수 점화식 찾기 13은 (13 - 1) 의 최소 제곱수의 합 + 1(13 - 4)의 최소 제곱수의 합 + 1(13 - 9)의 최소 제곱수의 합

실버 2 https://www.acmicpc.net/problem/159889095번 1,2,3 더하기 와 비슷한 문제입니다.다른 점은 n의 범위가 1 <= n <= 1,000,000 로 변했고 각 테스트 케이스마다 1,000,000,009로 나눈

실버 1https://www.acmicpc.net/problem/1149테이블 정의하기dpi = i번째 집일 때 집을 칠하는 최소 비용 점화식 찾기 i번째 집이 빨강일 때(0),i-1번째 집이 초록집이거나 파랑인 경우에 최솟값과 빨강일 때의 값을 더해줍니다.

실버 1 https://www.acmicpc.net/problem/1309테이블 정의하기Di = i번째 줄에 사자가 없어도 되는 경우 Di = i번째 줄, 1번째 칸에 사자가 있는 경우 Di = i번째 줄, 2번째 칸에 사자가 있는 경우 점화식 찾기i번째 줄에

실버 1 https://www.acmicpc.net/problem/11057테이블 정의하기Di = 수의 길이 i일 때, 오르막 수의 개수점화식 찾기 N = 1 한자리 수일 경우, 0~9경우 10가지N = 2 두자리 수일 경우, 0로 시작할 때, 10가지1로 시