백준/DP13

• 

  [백준 2688번 / C++] 줄어들지 않아 dp를 활용한 문제이다. #접근방법 제일 먼저 생각해야하는 것은 각 자릿수를 나타내는 dp배열을 생성해야한다. 예를 들어, dp[1][3] 은 첫번째 자릿수의 값이 3일 때! dp[2][1] 은 두번째 자릿수의 값이 1일 때! dp[4][0] 은 네번째 자릿수의 값이 0일 때! 그렇기 때문에, 먼저 dp[1][i] 를 1로 초기화 한다. 왜냐하면 첫 번째 자릿수의 각 숫자들은 오로지 하나만 존재할 수 있다. 그리고 dp[2][i] 를 갱신해나가야하는데, dp[2][0] 이라면 "00", "01", "02", "03" ..... "08", "09" 의 경우의 수가 있다 즉, dp[1][0]~ dp[1][9]의 합과 같다. dp[2][4] 라면 "44", "45", "46", "47", "48", "49" .. 백준/DP 2022. 4. 14.

• 

  [백준 15486번 / C++] 퇴사 2 dp를 활용한 문제이다 #접근방법 본인이 생성한 dp 배열의 의미는 해당 인덱스 값에 받을 수 있는 최댓값이다. 즉, dp[3] = 4 라는 것은 3일에 받을 수 있는 최댓값이다. 이 문제의 핵심은 1일에 상담을 시작하면 3일이 걸리니 받을 수 있는 금액은 4일에 받을 수 있다는 것이다. 다시 말해서, 1일에는 아직 금액을 받지 못하고 1일+3일 후에야 P1의 비용을 받을 수 있다. 즉, dp[1] 은 0이고 dp[4] = 10 이 되는 것이다. dp[2] = 0 이고, dp[7] = 20 dp[3] = 0 이고, dp[4] = 10이다. 이때, dp[4] 는 day가 1일일 때 dp[day(1일)+T1(3일)] = 10 라는 값이 세팅 되어 있으므로, dp[i+Ti] = max(dp[i+Ti], 현재까.. 백준/DP 2022. 3. 16.

• 

  [백준 11722번 / C++] 가장 긴 감소하는 부분 수열 dp 배열을 활용해서 풀면된다. #접근방법 본인은 증가수열이 매우 익숙해서 reverse 함수를 통해서 벡터의 순서를 바꿔주고 LIS(최장증가수열)를 통해 문제를 풀었다. dp 배열 1로 초기화, v 배열 데이터값 저장. v 배열 인덱스 1부터 n-1까지 돌면서 dp를 확인한다. 인덱스 i에 위치한 v 벡터의 데이터값과 인덱스값이 j (for (j.. 백준/DP 2022. 3. 15.

• 

  [백준 11057 / C++] 오르막 수 dp 배열을 이용해서 풀면된다. [dp이차원 배열 ] 길이/끝자릿수 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 6 7 8 9 10 3 1 3 6 10 15 21 28 36 45 55 예를 한번 들어보자. 만약 길이가 3인 오르막수를 구하라고 하면 어떻게 체크를 해야할까? 먼저 위의 표를 보면 길이를 나타내는 컬럼과 1~9까지의 자릿 수의 컬럼을 만들었다. 각 길이의 해당 끝자릿 수의 경우의 수는 현재 길이의 이전 끝자릿 수의 경우의 수 + 이전 길이의 같은 끝자릿수의 경우의 수이다. 즉, 위의 표에서 길이가 2이고 끝자릿 수가 1인 값은 2 이고, (01,11) 길이가 3이고 끝자릿 수가 0인 값은 1 라는 것을 알 수 있다. (000) 그렇다면 길이.. 백준/DP 2022. 3. 10.

• 

  [백준 4811번 / C++] 알약 dp배열을 생성하여 탑다운 방식으로 접근하면 된다. 탑다운 방식이란 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식 #접근방법 Test Case를 적당한 숫자를 예를 들어서 풀어보는 것을 연습해야한다. 본인은 숫자 3을 예를 들어서 풀어보았다. WWWHHH WWHWHH WWHHWH WHWWHH WHWHWH 이렇게 총 5가지가 나오는 것을 알 수 있다. DP를 어떻게 활용하냐? DFS를 수행할 때 두가지로 나뉘어서 재귀호출을 한다. 1. W인 알약을 집었을 때 W의 개수를 -1 해주고 H의 개수를 +1 해준다. 2. H인 알약을 집었을 때 H의 개수만 -1 해준다. 이 두가지 재귀 호출을 해서 받아온 리턴값을 더해서 DP 배열에 저장해준다. 리턴해주는 조건문은 H의 개수가 -1이 되었을 때. (경우의 .. 백준/DP 2022. 3. 8.

• 

  [백준 16194 / C++] 카드 구매하기 2 [백준 11052번 / C++] 카드 구매하기 DP를 활용한 문제이다. #접근방법 예를 들어 카드 3개를 사려고 한다. DP 배열의 인덱스 번호의 의미는 카드의 개수를 나타내고 카드의 개수만큼 살 수 있는 최댓값을 가지고 있다. 그렇다면 dp[3] baebalja.tistory.com 위의 문제와 똑같은 문제이지만 최솟값을 찾는 문제이다. 다른점은 dp의 초기 세팅을 cost로 해주는 점과 max 알고리즘 대신에 min으로 바꿔줬다. 11052번 문제를 풀지 않았다면 위의 링크를 들어가서 풀고나서 이 문제를 풀기를 추천한다. #include #include #include using namespace std; int main() { int n; cin >> n; vector cost(n + 1); vec.. 백준/DP 2022. 3. 8.

• 

  [백준 11052번 / C++] 카드 구매하기 DP를 활용한 문제이다. #접근방법 예를 들어 카드 3개를 사려고 한다. DP 배열의 인덱스 번호의 의미는 카드의 개수를 나타내고 카드의 개수만큼 살 수 있는 최댓값을 가지고 있다. 그렇다면 dp[3] 에는 카드 3개를 살 수 있는 최대 비용이라고 이해하면 된다. 1. dp[2] (두개를 샀을 때 최댓값) + cost[1] (카드 한장 묶음 비용) 2. dp[1] (한개를 샀을 때 최댓값) + cost[2] (카드 두장 묶음 비용) 3. dp[0] (0개를 샀을 때 최댓값) + cost[3] (카드 세장 묶음 비용) 즉 이 3가지의 최댓값을 dp[3]에 갱신해주면 된다. 점화식은 아래와 같다. " DP[i] =max( DP[i] , (DP[i-j] + cost[j])) " #include #include.. 백준/DP 2022. 3. 8.

• 

  [백준 1520번 / C++] 내리막 길 dp와 dfs를 활용한 문제이다. 어떤 착한 조상이 dfs라는 배를 타고 여행을 떠나는데 길을 잘 모르는 상태이다. 그래서 현재 위치(X)를 표시해주고 그 위치에서 갈 수 있는 "A,B,C,D"의 4개의 갈림길을 "A"부터 차례대로 여행을 계속한다. 결국 가고자하는 도착지점에 도착했을 때 아까 체크해주었던 현재 위치(X)로 돌아가고 "B"라는 갈림길로 또 여행을 간다. "D"까지 여행을 다하고 나서 현재 위치(X) 로 돌아온다. 근데 알고봤더니 "A,B,D" 의 갈림길은 도착지점으로 가는 경로였지만 "C"는 낭떠러지였다 그래서 착한 조상은 현재 위치(X) 라는 곳에 "A, B, D" 이 세개의 경로만 도착지점에 갈 수 있다고 "3"이라는 숫자를 새겨놓는다. 그 조상은 수많은 여행을 통해 "map[500].. 백준/DP 2022. 2. 24.

• 

  [백준 5557번 / C++] 1학년 DP를 활용한 문제이다. #접근방법 입력할 수 있는 개수 최대 100과 최대 sum값을 20을 가지기 때문에 dp[101][21] 배열 생성. 등호를 붙여야 하는 (index-2) 위치에 도달 할 때까지 dfs방식으로 호출한다. ("- 연산", "+ 연산" ) - sum값이 0보다 작거나 20보다 크면 return 0 - 이미 메모이제이션이 되있는 경우 해당 값을 return - (index-2) 위치에 도달했을 때 마지막값과 sum값이 같으면 return 1 (카운트) #include using namespace std; typedef long long ll; int n; ll dp[101][21]; ll d[101]; ll go(int idx, int sum) { if (sum 2.. 백준/DP 2022. 2. 22.

• 

  [백준 1149번 / C++] RGB거리 dp배열을 생성해서 풀면 된다. #접근방법 1. 2차원 dp 배열 생성한다. 2. 현재 dp값에 이전 dp 배열에서 다른 색을 가지고 있는 집들 중 작은 값을 선택해서 더해준다. 3. 최솟값 출력한다. #include #include #include #include using namespace std; vector v; int n; int result = INT_MAX; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; vector dp(n + 1, vector(3, 0)); for (int i = 1; i > dp[i][0] >> dp[i][1] >> dp[i][2]; dp[i][0] += min(dp[i - 1][.. 백준/DP 2022. 2. 17.