백준/동적프로그래밍51 백준 15990 c++ "1, 2, 3 더하기 5" -PlusUltraCode- https://www.acmicpc.net/problem/15990 [필자 사고]동적 프로그래밍 문제이다. 처음 이 문제를 봤을 때 당황했던 점은 연속된 수는 불가능 하다는 점이다.연속된 숫자가 가능하면 동적프로그래밍 계단 문제와 비슷한 알고리즘으로 풀 수 있는데 아쉬웠다.그런 다음 생각한 사고 방식이 이전에 사용한 숫자를 기록할 수단이 필요 했다는 점이다.그래서 필자는 2차원 방식을 생각을 했고 DP[N][3] 식으로 1,2,3을 닮을 공간을 마련해줬다.그런 다음 점화식은 dp[i][1] = dp[i-1][2] + dp[i-1][3] 형태로 구현했다. 현재 1이라는 숫자를 넣을거니깐 i-1칸으로 간뒤 이전값이 2와 3인 dp들의 값을 더하는 방식이다.위와 같은방법을 1,2,3을 반복하면 해당 문제를 .. 2025. 2. 21. 백준 12852 c++ "1로 만들기 2" -PlusUltraCode- https://www.acmicpc.net/problem/12852 [필자 사고]그래프 탐색으로도 풀 수있지만 필자는 동적프로그래밍을 이용하여 풀었다.이 문제를 풀면서 오랜만에 부모추적 알고리즘을 사용했다.매번 최소화 되는 지점마다 이전 idx의 위치를 현재 idx에 기록을 하게 되면 나중에 부모추적을 할 수 있게 된다. 또한 top-down 보단 bottom-up을 하는게 문제를 푸는게 훨씬 수월함을 느꼈다. [코드 해설]2. 유효한 숫자 검사 (isInside 함수)isInside(num) 함수는 num 값이 N 이하인지 확인한다.num ≤ N 이면 true 반환그렇지 않으면 false 반환이 검사는 N을 초과하는 연산을 방지하는 역할을 한다.3. 최소 연산 횟수 및 부모 노드 업데이트 (findMi.. 2025. 2. 17. 백준 1890 c++ "점프" -PlusUltraCode- https://www.acmicpc.net/problem/1890 [필자 사고]동적프로그래밍 문제이다.필자는 보통 이런 문제는 최대값을 구한는 문제 형태로 나온다.그래서 처음 필자가 생각한 풀이는 현재 지점에서 이전에 올 수 있는 경로들에서 최대값을 가져와서 반영한다"와 같은 식으로 점화식을 설계해 왔다. 그러나 이 문제는 현재 지점에서 다음으로 갈 위치에 값을 누적해서 더해주는 형태로 짜줘야 됐다. 사고의 전환이 일어나서 좋은 문제였던거 같다.[코드 해설]2. 입력 처리 (Input 함수)Input() 함수는 다음과 같은 역할을 한다.입력 처리cin >> N;을 통해 N 값을 입력받는다.arr 벡터와 dp 벡터를 크기 (N+1) x (N+1)로 동적 할당한다.격자 정보 입력arr[i][k] 값은 각 칸.. 2025. 2. 17. 백준 1309 c++ "동물원" -PlusUltraCode- https://www.acmicpc.net/problem/1309 [필자 사고]동적프로그래밍 문제이다.필자는 점화식을 다음과 같이 설계했다.1층 2층 3층 ... N층을 구별하고 빈곳 , 왼쪽, 오른쪽을 구별하기위해dp[N][3] 이 배열을 만들었다. 그리고 빈곳은 dp[N][0] 왼쪽 dp[N][1]오른쪽 dp[N][2] 으로 정했고dp[i][0] += (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2])%MOD; dp[i][1] += (dp[i - 1][0] + dp[i - 1][2])% MOD; dp[i][2] += (dp[i - 1][0] + dp[i - 1][1])% MOD; 다음과 같은 점화식을 이용하여 문제를 해결했다.이 문제를 통해 느낀점은 dp의 점화식을 세우.. 2025. 2. 17. 이전 1 ··· 3 4 5 6 7 8 9 ··· 13 다음
