DP
-
프로그래머스 2 x n 타일링프로그래머스(Programmers) 2022. 7. 7. 23:35
=> DP 문제입니다. => 점화식을 세울 줄 아는지에 대해 묻는 문제였습니다. => 위에서부터 아래로 CASE를 나누며 점화식을 만들어낼 수 있는지 확인하는 문제입니다. => 혹은, F(n)의 값들을 써보며 규칙성을 찾아 문제를 풀이할 수도 있습니다. => 해당 문제는 피보나치수열과 같은 문제였습니다. => 풀이는 아래에 첨부하였습니다. #include #include #include #include using namespace std; int solution(int n) { vector answer; answer.push_back(0); answer.push_back(1); answer.push_back(2); if((n==1) || (n==2)) { return answer[n]; } for(int..
-
N으로 표현 C++프로그래머스(Programmers) 2022. 1. 2. 10:45
입출력 예 N number return 5 12 4 2 11 3 입출력 예 설명 예제 #1 문제에 나온 예와 같습니다. 예제 #2 11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다. #include #include #include #include // unorderd_set사용 using namespace std; int get_basic(int N, int cnt) { int res = 0; while (cnt > 0) { cnt -= 1; res += N * pow(10, cnt); } return res; } int solution(int N, int number) { int answer = -1; vector s(8); int idx=1; if(N == number) { ret..
-
백준 1149 - RGB거리백준 algorithm 2020. 7. 4. 02:01
=> DP문제입니다. => 오랜만에 푸는 문제인지라 이해하는데 오래 걸렸습니다. => 빨간색을 칠하기 위해서는 이전에 초록색 혹은 파란색이 칠해져 있어야 합니다. =>이 경우, 둘 중에 최소값을 골라 해당하는 집에 빨간색을 칠하는 금액에 더해주어야 합니다. 파랑 or 초록 (1번째 집) 빨강 (2번째집) => 위의 방식처럼 이루어져야 합니다. =>2번째 집에 빨강을 칠하고 싶을 경우, 이전의 집의 색이 파랑 혹은 초록이어야 합니다. **주의할 점 : row가 0인 지점부터 값을 넣어줄 경우 (0-1) 지점을 참조할 수 있으니 실수하지 않도록 합니다. 점화식은 아래와 같습니다. dp[i][0] += min(dp[i-1][1] , dp[i-1][2]); dp[i][1] += min(dp[i-1][0] , d..
-
백준 11053 - 가장 긴 증가하는 부분 수열백준 algorithm 2020. 5. 9. 12:42
=> DP 문제이다. => 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. => 수열 A =[10, 20, 10, 30, 20 ,50] => 가장 긴 증가하는 부분 수열 A = [10, 20, 30, 50] => D[N] : A[i] 를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 => D[i]는 A[i]를 반드시 포함하여야 한다. => 위의 그림을 보면 어떤 방식으로 이루어지는지 알 수 있다. **가장 긴 증가하는 부분 수열 구하는 알고리즘 for(int i=0; i N; for(int i=0; i> A[i]; } int D[N]; for(int i=0; i
-
백준 2193 - 이친수백준 algorithm 2020. 4. 23. 17:39
=> DP 문제이다. => DP [i][j] => i : 몇 자릿수인지 나타냄 => j : 어떤 숫자로 끝나는지 나타냄 DP[i][0] = DP[i-1][0] + DP[i-1][1] => 0으로 끝나는 수의 경수, 앞의 수가 1이어도 되고 0이어도 된다. DP[i][1] = DP[i-1][0] => 1으로 끝나는 수의 경수, 앞의 수가 0이어야 된다. 위의 식대로 풀어도 된다. 본인은 하나씩 손으로 풀어보며 식을 세우게 되었다. DP[i] = DP[i-1] + DP[i-2] => 위의 식을 통해 원하는 값을 얻을 수 있다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr)..
-
백준 15990 - 1, 2, 3 더하기 5백준 algorithm 2020. 4. 23. 16:29
=> DP 문제이다. => 기존 문제아 달리 이차원 배열로 하여 문제를 해결하여야 한다. dp[i][j] : i를 1,2,3의 합으로 나타내는 방법의 수, j : 마지막에 사용한 수 dp[i][1] : 바로 전에 사용할 수 있는 수는 2,3 dp[i][2] : 바로 전에 사용할 수 있는 수는 1,3 dp[i][3] : 바로 전에 사용할 수 있는 수는 1,2 if (n - 1 >= 0) { dp[n][1] = (dp[n - 1][2] + dp[n - 1][3]) % mod; } if (n - 2 >= 0) { dp[n][2] = (dp[n - 2][1] + dp[n - 2][3]) % mod; } if (n - 3 >= 0) { dp[n][3] = (dp[n - 3][1] + dp[n - 3][2]) % ..
-
백준 11052 - 카드 구매하기백준 algorithm 2020. 4. 14. 15:42
=> DP 문제입니다. => 카드 i개를 구매할 때의 최대 비용을 생각해야 합니다. => D[i] : 카드 i개 구매하는 최대 비용 =>카드 i개를 구매하는 방법의 가짓수 카드 1개 들어있는 카드팩 구매, 카드 i - 1개 구매 카드 2개 들어있는 카드팩 구매, 카드 i - 2개 구매 .... .... .... 카드 i 개 들어있는 카드팩 구매, 카드 0개 구매 이를 나타내면 P[1] + D[i-1] 위와 같이 표현할 수 있습니다. 이를 코드로 표현하면 for(int i=1; i N; vector P(N+1); vector D(N+1); int tmp; for(int i=1; i> tmp; P[i] = tmp; } for(int i=1; i
-
백준 1463 - 1로 만들기백준 algorithm 2020. 4. 6. 00:34
=> DP 문제이다. => 내가 구해야 하는 것을 우선적으로 문자로 써본다. 내가 구하고자 하는 것 : N 을 1로 만드는데 필요한 최소 연산 횟수 가능한 경우의 수 : 1. i 가 3으로 나누어 떨어질 때 - arr[ i/3 ] + 1 2. i 가 2로 나누어 떨어질 때 - arr[ i/2 ] + 1 3. i 에서 1을 뺄 때 - arr[ i - 1 ] + 1 => 위의 경우 세 가지가 있는 것을 알 수 있다. => DP에는 Top-down 방식과 Bottom-up 방식이 있다. => 본인은 Bottom-up 방식을 선호한다. (Top-down은 재귀를 쓰는데, 재귀를 쓰다 보면 헷갈린다....) *** 둘 중 어느것이 좋다는 것은 없다. 본인이 원하는 방식으로 사용하면 된다. #include #inc..