BOJ/DP
[C++] BOJ 9251 / DP (LCS 최장 공통 부분 수열)
코드 #include #include #include using namespace std; int same[1002][1002]; int main() { ios::sync_with_stdio(0); cin.tie(0); string a, b; cin >> a >> b; int lenA = a.size(); int lenB = b.size(); for(int curA=1;curA
[C++] BOJ 2579 / DP (계단 오르기, 점화식 2차원 배열 접근)
코드 #include #include using namespace std; int stairs[301]; int arr[301][2]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i> stairs[i]; } arr[0][1] = stairs[0]; arr[1][2] = arr[0][1] + stairs[1]; arr[1][1] = stairs[1]; for(int i=2;i 2칸 째에 i번 계단을 밟았을 때의 최대 점수 점화식 arr[i][1] = max(arr[i-2][1], arr[i-2][2]) + stairs[i] arr[i][2] = arr[i-1][1] + stairs[i]
[C++] BOJ 9095 / DP (1, 2, 3 더하기)
문제 분석 https://www.acmicpc.net/problem/9095 해당 문제도 DP로 해결해야 한다. DP의 경우에는 정말 어려운 문제가 아닌 이상, 문제 분석과 해결 방법은 생략하겠다. 코드 #include using namespace std; int arr[12] = {0,1,2,4,0,0,0,0,0,0,0,0}; int main() { int t, n; cin >> t; while(t--) { cin >> n; if(n
[C++] BOJ 1463 / DP (1로 만들기, 점화식 첫 도전)
문제 분석 https://www.acmicpc.net/problem/1463 BFS로도 구현이 가능하지만, DP로 훨씬 깔끔하게 구현이 가능하다. 어떠한 문제에 DP를 적용해야 하는지 깨닫기 위해서는 많은 문제를 풀면서 습득해야 한다. 해결 방법 DP 문제는 공통적인 해결 방법을 갖는다. 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정의하기 이다. 코드 #include #include using namespace std; int arr[1000001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=2;i