본문 바로가기

백준/동적프로그래밍49

백준 1106 c++ "호텔" -PlusUltraCode- https://www.acmicpc.net/problem/1106 [필자 사고]동적 프로그래밍 문제이면서 배낭 문제이다.이번에 필자는 탑다운 방식으로 문제를 해결해 나갔따.탑다운 방식은 뮤탈리스크 문제를 통해 배웠었다.  필자가 푼 사고 과정은 다음과 같다.dp[N] 매번 시행 마다 N-person 을 해줘서 처음 0보다 작거나 같을 때 순간까지 구해주는 방식으로 해결했따. [코드 해설] 입력 처리 (Input 함수)Input() 함수는 호텔 홍보 목표 고객 수(C)와 홍보할 수 있는 도시의 개수(N)를 입력받는다. 이후 각 도시에서 홍보할 때 필요한 비용과, 그 비용을 지불했을 때 얻을 수 있는 고객 수를 입력받아 벡터 arr에 저장한다. 입력이 완료된 후 동적 프로그래밍을 위한 배열인 dp를 목표 고.. 2025. 3. 15.
백준 12869 c++ "뮤탈리스크" -PlusUltraCode- https://www.acmicpc.net/problem/12869 [필자 사고]동적프로그래밍 문제이다.처음으로 탑다운 방식으로 문제를 해결한 문제이다.약간의 나의 사고를 여기다 적어 보겠다.초기 dp접근했을 때 값은 다 없다.만약 다 없다고 하면 최대값을 넣는다.그리고 가야할 구간을 적용시킨다.그런데 만약 값이 -1이 아니라면 return 으로 해당 값을 반환한다.이미 값이 결정됐따는 의미다. 그리고 초기에 if문을 이용하여 범위 검증을 통해 완수한다.탑다운 방식은 아직 익숙치 않아서 다소 어려움이 있었다.  아래는 자세한 코드 해설이다.[코드 해설]2. 입력 처리첫 번째 줄에는 몬스터의 개수를 나타내는 정수 NNN이 입력된다. 두 번째 줄에는 각 몬스터의 체력이 주어지며, 최대 3마리까지만 존재하기 .. 2025. 3. 14.
백준 2631 c++ "줄세우기" -PlusUltraCode- https://www.acmicpc.net/problem/2631 [필자 사고]가장 큰 증가하는 수열 관련 문제이다.다만 LIS를 통해 구한 값에 N- LIS 아이디어를 떠오르는건 쉽지 않았을 것 같다.필자는 처음에 바로 아이디어가 떠오르지 않았고 작은 수부터 차근차근 해보니 혹시 이러지 않을까 하는 직감..?? 으로 해보니 일관된 답들이 나올 수 있어서 알고리즘을 작성했따.[코드 해설]1. 입력 처리 (Input 함수)먼저, 프로그램은 사용자로부터 수열의 크기를 입력받는다. 이 크기를 기준으로 두 개의 벡터를 선언하는데, 하나는 실제 수열을 저장하는 arr 벡터이며, 다른 하나는 각 원소를 마지막으로 하는 최장 증가 부분 수열의 길이를 저장하는 dp 벡터이다.이 dp 벡터는 모든 원소를 최소한 자기 자.. 2025. 3. 12.
백준 10942 c++ "팰린드롬?" -PlusUltraCode- https://www.acmicpc.net/problem/10942[필자 사고]해당 문제는 동적프로그래밍을 이용하여 풀어야 되는 문제이다.다만 필자는 해결법을 찾지 못해였다.구글링을 통해 문제푸는 방식을 이해를 하였고 해다 사고 과정을 여기에 적겠다.dp[][]를 2차원으로 정의했고 정의를 말해보자면 시작점과 끝점을 의미한다. dp[1][3] 이라고 한다면 첫번째 배열과 3번째 배열을 의미한ㄷ. 다음으로 하나의 글자는 반드시 펠린드롬이기 때문에 dp[1][1] ... 형태는 모두 1이라는 값으 넣어주었다.그리고 추후 알고리즘을 구현하는데 있어서 2글자는 미리 사전에 설정해 주었따.arr[i]==arr[i-1] 이 같다면 dp[i-1][i] =1 을 넣어주었다. 마지막 알고리즘은 바깥쪽 for 문은 길이를.. 2025. 3. 12.

티스토리툴바