본문 바로가기

백준/동적프로그래밍51

백준 11054 c++ "가장 긴 바이토닉 부분 수열" -PlusUltraCode- https://www.acmicpc.net/problem/11054 [필자 사고]동적 프로그래밍 문제이다.언뜻 봤을 때는 LIS문제 같아 보이지만LIS문제를 응용한 문제이다.dp배열을 2개 만들어 시작부분과 끝부분에서 각 시작하여 각 인덱스마다 2개의 배열을 더한 값-1 이 가장 큰값을 출력해야 된다. 필자는 해당 LIS를 구할 때 초기값을 1 로 설정을 안해서 출력값이 계속 1보다 작은 문제가 발생했었다.이 부분 주의해야 겠다. 개인적으로 해당 문제에서 LIS지식을 2개를 이용하여 처음 부분과 끝부분으로 알고리즘 적용한게 인상적이였다.[코드 해설]입력 처리 (Input 함수)Input() 함수는 배열의 크기 N을 입력받고, 이를 기반으로 배열 arr, dp, rDp를 초기화한다.arr 배열은 입력받은 .. 2025. 3. 10.
백준 2293 c++ "동전 1" -PlusUltraCode- https://www.acmicpc.net/problem/2293 [필자 사고]LIS 문제를 이용한 dp문제이다.다만 다른점은 경우의 수를 구해야 되는 것이다.LIS문제는 +1형태로 계속 누적하는 거지만 경우의 수는이전 수를 += 형태로 더해나가야 된다. 필자는 +=이 부분을 생각을 하지 못하여 풀지 못했다.경우의 수는 누적 더하기라는 교훈을 알게 되었다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 먼저 표준 입력을 통해 동전의 개수(N)와 목표 금액(K)을 입력받는다. 이후, 동전 정보를 저장할 coin 벡터를 크기 N+1로 할당하고, 결과를 저장할 dp 벡터를 크기 K+1로 초기화한다.그 후, 사용자가 입력한 동전의 가치를 coin 벡터에 저장한다.3. DP를 이용한 해결 (G.. 2025. 3. 9.
백준 14728 c++ "벼락치기" -PlusUltraCode- https://www.acmicpc.net/problem/14728 [필자 코드]기본적인 배낭알고리즘 문제이다.배낭 알고리즘의 본인만의 팁은 현재 값에서 특정값까지 하나하나 갱신해 간다는 느낌으로 하면 쉽게 문제를 해결할 수 있다.다만 배낭문제에서 작은거에서 큰거로 접근하게 되면 중복되는 값이 발생할 수 있다.그래서 끝에서 부터 접근해야 된다. 큰곳에서 작은곳으로이 문제를 풀면서 알게 된 사실이다.[코드 해설]2. 입력 처리먼저, N과 T를 입력받는다. 여기서 N은 선택할 수 있는 항목의 개수이며, T는 총 제한된 시간이다. 그런 다음, dp 벡터를 크기 T+1로 설정하여 각 시간에 대해 얻을 수 있는 최대 점수를 저장한다.3. 동적 계획법을 이용한 최적해 탐색각 항목에 대해 K(소요 시간)와 S(얻을 .. 2025. 3. 8.
백준 4811 c++ "알약" -PlusUltraCode- https://www.acmicpc.net/problem/4811 [필자 사고]DP 탑다운 및 바텀업 둘다 가능한 문제다.필자는 바텀업 방식으로 풀었고 해당 문제만의 특이한 매력은W가 반드시 먼저 와야 된다는 제약조건이다.즉 바텀업 방식으로 구현할때 H가 W보다 크면 절대로 안된다.반드시 H는 W보다 작아야 된다.사소한거지만 이러한 조건하나가 문제를 풀수 있을지 못할지를 결정하는걸 배웠따. 아래는 상세한 코드 해설이다.[코드 해설]2. DP 테이블 정의이 문제에서 DP 테이블 dp[w][h]는 다음을 의미합니다:w: 아직 쪼개지 않은 (Whole) 알약 개수h: 이미 반으로 쪼개져 있는 (Half) 알약 개수dp[w][h]: W(Whole)를 w개, H(Half)를 h개 사용했을 때 만들 수 있는 문자열.. 2025. 3. 6.

티스토리툴바