"(백준/ C++) 1010 - 다리 놓기 / 다이나믹 프로그래밍, 재귀"https://www.acmicpc.net/problem/1010 N을 늘려보면서 비교를 해보니 규칙을 쉽게 발견 할 수 있었다. N(강 서쪽)의 맨 위 다리가 M(강 동쪽)에 위치할 수 있는 조건은 N은 빠짐 없이 모두 연결은 되야 하므로 M - N + 1이 된다. DP [ N ][ M ] 이라고 만들 때, 아래 그림과 같이 규직을 찾을 수 있는데 N이 1일때는 M의 개수 만큼 경우의 수가 생긴다. 이 조건은 함수의 return(반환) 조건으로 사용하면 된다.또 N과 M이 같을 때는 모든 다리를 연결 하므로 언제나 하나의 경우의 수이다. 이거 또한 함수의 return(반환)조건으로 사용한다. N(강 서쪽)의 맨 위 다리를 M(강 ..

"(백준/ C++) 1520 - 내리막길 / 다이나믹 프로그래밍" 이건 DP 중 어려운 문제에 속하는게 아닌거 같은데 잘못 생각해서 계속 틀렸다.. 처음 생각했을 때 높은 곳에서 낮은 곳으로 이동한다고 해서 위로 ↑ 갈 수 없다고 생각했는데 높은 곳과 낮은 곳의 기준은 배열 안의 숫자지 배열의 위치를 따지는 것이 아니다. 그럼 즉  → 우  ↑ 위   ← 좌  ↓ 아래 모두 가능하다.  다른 사람들의 풀이를 보면 0, 0 부터 M-1, N-1까지 오는 경로에만 1을 리턴 해준다. 나는 거꾸로 생각했고, 목적지 부터 스타트 까지 갈 수 있는 방법으로 구현했다. 사실 상 같다.  그리고 나처럼(?) 바보같이 모든 if문을 나누지 말고.. for문을 이용하자. 다른 사람들의 문제 풀이를 보면 좌,우,상,하 모..

"(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍" 해도해도 어려운 DP .. 혼자 못 풀었다. 유투브 설명 보고 풀었다 .. ㅠㅠ 핵심은 AEH 사이의 (ABCDE) (FGH)가 어떠한 방법으로 연산을 했든지 간에 (ABCDE) 의 최종행렬의 크기는 { a , f } (FGH)의 최종행렬 크기는 { f , i }가 된다. 라는 사실이다.  점화식:  a x f x i + Func(x , k) + Func (k+1, y)    //== [ 행렬 곱셈 순서 ] ==#include #include #include using namespace std;int col[500], row[500];int dp[500][500];int func(int idx_x, int idx_y){ if (d..

" (백준/ C++) 7579 - 앱 "  https://www.acmicpc.net/problem/7579 7579 - 앱입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다.www.acmicpc.net 다이나믹 프로그래밍으로 풀어야 하는 문제. 처음에는 무게로 DP를 만들면 되겠다 ~ 했지만 ?? 무게(M)이 최대 10,000,000 이였다. DP[ n ][ m ] 이건 ..

" (백준/ C++) 1106 - 호텔 " https://www.acmicpc.net/problem/1106 1106 - 호텔첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.www.acmicpc.net 이 문제는 냅색과 비슷하다.다른 점이 있다면 중복으로 넣을 수 있는 점? 냅색 문제는 물건 하나 씩 넣는다. 가장 간단해보이는 예제 입력1번을 보고 DFS를 이용하여 풀 수 있는 방법을 고민해봤다.  " C명(12명)을 확보하면서 최소의 비용이 들어..

11660번: 구간 합 구하기 5 (acmicpc.net) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 다이나믹 프로그래밍 1. "11659 - 구간 합 구하기4"를 2차원으로 변형한 문제라고 접근했다. 2. 동일한 크기의 행렬을 하나 더 만들어 입력을 받는 동시에 이전의 합과 현재값을 더하여 index 1 ~ index 현재까지의 합을 구해주었다. 3. begin : (x1, y1) end: (x2, y2) 로 구분하여 end부터 begin까지의 합을 구해주었다...