fatalite

문제 링크 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이 문제를 풀려고 했는데, 2차원 DP 문제일까 생각을 해봤지만, 고민해봐도 비교하는 것과 규칙이 생각나지 않아서 해설을 봤다. 잘 알려진 문제인 것 같다 최장 부분 증가 수열, LIS라고 불리는 문제이다. 근데 이거의 베이스 문제가 이미 풀었던 문제였더라, 아마 해답 보고 다시 생각해보지 않아서 그랬나보다.. 복습을 해야겠다. DP 문제의 핵심은 어떻게 부분 문제로 나눌 것인가가 핵심인 것 같다. 다양한 시도가 필요해보인다. 11053번: 가장 긴 증가하는 부분 수열 수..

문제 문제 난이도 : 실버 1 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 나머지 연산 생각해볼 필요가 있을 듯 하다 문제 소스코드 #include #include #include #include #include #include #include #include using namespace std; long long DP[1001][10]; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); std::cout.tie(NULL); } int main() { Init(); int n; cin >> n; for (int i = 0; i < 10; i++) { DP[1][i] = 10 - i; } for (int i = 2; i

문제 분류 문제 난이도 : 실버 1 문제 분류 : 다이나믹 프로그래밍 문제 리뷰 DP[j]를 j 개를 구매하는데에 걸리는 카드의 수로 정의한다.당연하게도, DP[0] = 0첫 번째 루프(i=1)에는 P_1만을 이용한다. DP[j] = P_1 * j가 된다.두 번째 루프(i=2)부터 비교를 해야한다. DP[j] = max(DP[j - 2] + P_2, DP[j]) 초록색 부분은 i = 1일 때의 값이었을 것이다....따라서 DP[j] = max(DP[j - i]+ P_i, DP[j])가 된다. 문제 소스코드 #include #include #include #include #include #include #include #include using namespace std; long Price[10001]; ..