본문 바로가기

백준/동적프로그래밍49

백준 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.
백준 1965 c++ "상자넣기" -PlusUltraCode- https://www.acmicpc.net/problem/1965 [필자 사고]가장 긴 증가하는 부분수열 관련 문제이다.자세한 설명은 아래 코드해설 부분에서 하겠습니다. 이 문제를 풀면서 조심해야 될점은 dp를 처음 초기화 할 때 1로 초기화 해야 된다.그 이유는 일단 자신의 갯수를 포함시켜야 하기 때문이다. 이 문제를 풀면서 받은 인상은 특정 인덱스를 고른 뒤 그 앞에 있는 애들을 조사하고현재 고른 인덱스의 값보다 작다면 dp를 갱신하는 작업을 수행한다.로 느꼇다. [코드 해설]1. 입력 처리 (Input 함수)N을 입력받아 배열의 크기를 결정한다.arr 벡터를 크기 N+1로 설정하여 입력 값을 저장한다.dp 벡터를 크기 N+1로 설정하고, 모든 값을 1로 초기화한다.dp[i]는 arr[i]를 마지막 .. 2025. 2. 10.
백준 15988 c++ "1, 2, 3 더하기 3" -PlusUltraCode- https://www.acmicpc.net/problem/15988  [필자 사고]점화식을 세우기 쉬운 dp문제이다.주목해야 될 숫자들은 1, 2,3, 이다.계단식 문제와 같은 풀이를 진행해주면 쉽게 풀 수 있다. 상세한 내용은 아래에 적어 놓겠다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] [코드 해설]1. 동적 계획법 (DP) 배열 초기화 (Make_DP 함수)Make_DP 함수는 최대 1,000,000까지의 정수를 다룰 수 있도록 DP 배열을 초기화하는 역할을 한다.dp 벡터를 크기 1,000,001로 설정한다.점화식 기반으로 DP 배열을 채운다.dp[1] = 1 → 1을 만드는 방법: {1}dp[2] = 2 → 2를 만드는 방법: {1+1, 2}dp[3] = 4 → 3을 만드.. 2025. 2. 10.

티스토리툴바