벨에삐

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 기본 DP 문제입니다. #include using namespace std; int N, P[1001], dp[1001]; void solve(){ for(int i = 1; i P[i]; } solve(); } dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다. 1) table 정의 dp[i] : i개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 기본적인 DP 문제입니다. #include using namespace std; int N, dp[100001]; void solve(){ memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for(int i = 1; i = 1; --j){ dp[i] = min(dp[i], dp[i-j*j] + 1); } } cout > N; solve..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 기본적인 DP 문제입니다. #include using namespace std; const int MOD = 10007; int n, dp[1001]; void solve(){ dp[1] = 1; dp[2] = 3; for(int i = 3; i n; solve(); } dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다. 1) table 정의 dp[i] : 2×i 크기의 직사..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이번에도 기본 DP 문제입니다. #include using namespace std; const int MOD = 10007; int n, dp[1001]; void solve(){ dp[1] = 1; dp[2] = 2; for(int i = 3; i n; solve(); } dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성 있게 풀이합니다. 1) table 정의 dp[i] : 2..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 이번에도 기본 DP 문제입니다. #include using namespace std; const int MOD = 15746; int N, dp[1000001]; void solve(){ dp[1] = 1; dp[2] = 2; for(int i = 3; i N; solve(); } dp 문제는 항상 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다. 1) tabl..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이번에도 DP 기본 문제입니다. #include #define ll long long using namespace std; int N; ll dp[91][2]; void solve(){ dp[1][0] = 0; dp[1][1] = 1; for(int i = 2; i N; solve(); } 항상 같은 패턴입니다. dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 기본적인 DP 문제입니다. #include using namespace std; const int INF = 0x3f3f3f3f; int n, k, coin, dp[10001]; set coins; void solve(){ memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for(int i = 1; i dp[i-c]+1) dp[i] = dp[i..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이번에도 DP 기본 문제입니다. #include using namespace std; int T, n, score[3][100001], dp[100001][3]; void solve(){ dp[1][0] = 0; dp[1][1] = score[1][1]; dp[1][2] = score[2][1]; for(int i = 2; i > n; for(int i = 1; i score[i][j]..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 기본적인 DP 예제입니다. 1) bottom-up 풀이 #include using namespace std; int N, dp[1000001]; void solve(){ dp[1] = 0; for(int i = 2; i dp[i/3] + 1) dp[i] = dp[i/3] + 1; if(i % 2 == 0 && dp[i] > dp[i/2] + 1) dp[i] = dp[i/2] + 1; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N; solve(); ..

https://www.algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. www.algospot.com #include using namespace std; int C, N, subseq[501], mx; int dp[501]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> C; while(C--){ memset(dp, 0, sizeof(d..