다이나믹 프로그래밍 (3) 썸네일형 리스트형 [C++] BOJ-1932 문제풀이 1. 가장 왼쪽에 있는 숫자와 가장 오른쪽에 있는 숫자는 경우의 수가 하나이기 때문에 바로 위에 배치된 숫자만 더하면 된다. 2. 그 외의 숫자들은 모든 경우의 수를 계산해서 가장 큰 수를 다음 줄에 저장한다. #include #include using namespace std; int main(){ int n; cin >> n; int dp[501][501]; for(int i = 0; i dp[i][j]; } } for(int i = 1; i [C++] BOJ-1699 문제풀이 1. cache배열의 인덱스 값을 제곱수로 생각하고 점화식을 구현하였다. cache[j] = min(cache[j], cache[j-dp_pow(i)]+1) 2. 전체 소스 #include using namespace std; int dp_pow(int a){ return a*a; } int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int cache[N+1] = {}; for(int i = 1; i [C++] BOJ-1520 문제풀이 1. 백트래킹 + DP를 이용해서 풀었다. 2. 재귀함수를 통해 모든 경우의 수를 백트래킹으로 탐색하지만 그 중에서 이미 탐색했던 부분이 있으면 그 곳은 다시 탐색하지 않는다. 3. 좌표(N,M)에 도착하면 결과값에 return값에 1씩 더해준다. #include #include using namespace std; int dx[4] = {0,0,-1,1}; // 상하좌우 int dy[4] = {1,-1,0,0}; int arr[500][500]; int cache[500][500]; int N,M; int func(int x, int y){ if(cache[x][y] != -1) return cache[x][y]; if(x == M-1 && y == N-1) return 1; cache[x][.. 이전 1 다음
