다이나믹 프로그래밍3 [백준] 16395: 파스칼의 삼각형(C++) 문제https://www.acmicpc.net/problem/16395풀이삼각형 형태를 좌측 정렬하여 2차원 배열로 생각해서 푸면 되는 문제이다. 배열을 pascal[i][j]이라고 가정할 때, j = 0, j = i인 경우에는 모두 1을 저장한다.그 외의 값들은 위 행의 인접한 두 수를 더하면 되는데, 2차원 배열이므로 식을 아래처럼 만들 수 있다. pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j] 코드#include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; int pascal[31][31]; for (int i = 0; i 2025. 4. 29. [백준] 9625: BABBA(C++) 문제https://www.acmicpc.net/problem/9625해결방법간단한 DP 문제이다.dp 배열을 [버튼 누른 횟수][A or B] 형식으로 사용할 것이기에 dp[46][2]로 선언해준다.dp[i][0]은 버튼을 i번 눌렀을 때 A의 개수, dp[i][1]은 B의 개수이다. 버튼을 누른 후 B는 BA로, A는 B로 바뀌므로 A와 B의 개수를 구하는 식은 다음과 같다.A의 개수 = 버튼을 누르기 전 B의 개수B의 개수 = 버튼을 누르기 전 A의 개수 + B의 개수 따라서 식으로 정리해보자면,dp[i][0] = dp[i-1][0]dp[i][1] = dp[i-1][0] + dp[i-1][1] 코드#include using namespace std;int main(){ ios::sync_with_st.. 2025. 4. 26. [C++] 백준 1520: 내리막길 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해결방법 dfs와 dp를 사용해서 풀 수 있는 문제이다. dp[x][y]에 저장되는 값은 (x, y)에서 (n-1, m-1)까지 가는 방법의 개수이다. 제일 왼쪽 위 (0,0)에서 현재 위치의 값보다 작은 방향으로 이동하면서 d[x][y] += dfs(nx,ny) 식을 통해 dfs를 돌려 다음 위치의 dp값을 받아오면 된다. 코드 #include using namespace std; int n, .. 2023. 10. 8. 이전 1 다음