Algorithm/Dynamic Programming (12) 썸네일형 리스트형 [백준] 2662번 기업투자 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 1만원 단위로 최대 N ( = 300 )까지의 액수를 최대 M ( = 20) 개의 회사를 선택해야기 때문이다. 300.C.20 -> 시간 초과 (2) DP 배열 정의 -> DP[N][M] : M 기업에 N 금액의 투자를 했을 경우 얻을 수 있는 최대 이익금 (3) 풀이 방법 -> investment[현재 보유하고 있는 금액][투자금액]으로 해결할 수 있다. 최대 이익금을 얻었을 때 각 기업에 얼마룰 투자했을 때 얻을 수 있는지 그 상태를 출력해야하는 부분을 신경써야한다. 자세한 내용은 아래 소스 코드 주석을 참고하자. 2. Source Code #include #include #include #include #define MAXC.. [백준] 1563번 개근상 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 브루트포스로 문제 풀이를 생각해보면 시간 초과가 나기 때문에 메모이제이션을 이용해서 풀이해보도록 한다. N이 1000이고 지각 2번, 결석 3번에 대한 모든 조합을 생각해보면 서로 다른 알파벳 3개 중에 1번은 1000개 중복, 2번은 2개 중복, 3번은 3개 중복이므로 #중복조합 은 n.H.r={n+r-1).C.r -> 이가 된다. ( '.' 콤마는 순열, 조합 기호 표시를 가시적으로 잘 보여주기 위해 임의로 삽입 ) 서로 다른 (n + r - 1)개의 수 중, r개를 뽑는 경우의 수 )로 1002.C.2 가 되고 1000000 연산이 필요한데 n이 1 ~ 1000 에 따른 모든 수를 구하기 위해서는 시간 초과가 나게 됩니다.. [백준] 4883번 삼각 그래프 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 (100,00, 3) 의 그래프를 1초 ( 약, 1억번의 연산 ) 내에 전부 탐색하려면 메모이제이션이 반드시 필요하다. (2) DP 배열 정의 -> DP[N][4] : N행, 1 - 3 열까지의 정점까지는 오는데에 필요한 최소 비용 (3) 풀이 방법 -> 아래 그래프와 같이 정점 -> 정점으로 가는 방향은 (아래, 오른쪽, 오른쪽 아래, 왼쪽 아래) 이므로 4가지 방향에 대해서 탐색을 한다. 그래프 범위 내에 있는 경우만 탐색하면된다. (4) 함정 -> 마지막으로 입력받는 0이 처음에 입력받는 수열 길이 N을 말하는 것 ( 무한루프 사용으로 해결 ) 2. Source Code #include #include #include #de.. [백준] 2565번 전깃줄 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 전봇대 A와 연결되어 있는 전깃줄에 대해서 정렬하고 LIS를 수행한다. (2) 풀이 방법 -> (1)번에서 설명한 방식대로 접근하면 쉽게 해결 가능하다. 2. Source Code #include #include #include using namespace std; int n; vector a;// first : A // second : B int dp[101]; int main() { int x, y;// x -> y cin >> n; for (int i = 1; i > x >> y; a.push_back(make_pair(x, y)); } // 정렬 수행 sort(a.begin(), a.end()); // LIS 수행 for (int.. [백준] 11053번 가장 긴 증가하는 부분 수열 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> KOI 유전자가 될 수 있는 최대 길이를 문자열의 처음, 끝부터 분할해나가면서 확인한다. (2) DP 배열 정의 -> dp[i] 는 i 번째 인덱스 까지의 배열 중 가장 긴 부분수열의 길이. (3) 풀이 방법 -> 내부 for문을 1부터 j - 1 까지 돌리면서 a[j] dp[i] ( 현재 i 인덱스의 가장 긴 부분수열의 길이 보다 큰 경우에) 2. Source Code #include #include using namespace std; int n; int a[1001]; int dp[1001]; int main() { cin >> n; for (int i =.. [백준] 2306번 유전자 문제 위치 : https://www.acmicpc.net/problem/2306 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> KOI 유전자가 될 수 있는 최대 길이를 문자열의 처음, 끝부터 분할해나가면서 확인한다. (2) DP 배열 정의 -> DP[s][e] : start 부터 end 까지 KOI의 최대 길이 (3) 후기 1. 문자열의 특정 패턴, 조건 등으로 길이를 구할 때 사용할 수 있다. 2. Source Code #include #include #include #include #define MAX 500 #define START0 'a' #define END0 't' #define START1 'g' #define END1 'c' using namespace std; /* .. [백준] 1006번 습격자 초라기 문제 위치 : https://www.acmicpc.net/problem/1006 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 영역별로 묶을 수 있는 (최대 2개) 영역들을 표시해나가면서 경우에 따라 재귀함수를 호출하면서 메모이제이션 한다. 영역의 상태는 아래와 같이 가정하였고 prev, last가 이 상태를 나타낸다. 0 -> not used 1 -> inner used 2 -> outer used 3 -> both used 위 상태를 정의하면서 상황에 맞게 따라나가면서 문제를 풀어나가는 방식이다. (2) DP 배열 정의 -> DP[idx][prev][last] : idx까지 이전 블록의 상태가 prev 이고 마지막 블록 n - 1 상태가 last 일 때 까지의 최소 초라기 수 (.. [백준] 11568번 민균이의 계략 문제 위치 : https://www.acmicpc.net/problem/11568 1. Approach (1) LIS( Longest Increasing Sequence) 로 접근한다. -> LIS는 다이나믹 프로그래밍 문제 중에서도 대표적인 문제이자, 많이 사용되는 풀이 방법 중 하나이므로 정확히 이해하고 지나가는 것을 권장한다. 아래 링크에서 LIS 풀이 방법을 확인 할 수 있다. https://blog.naver.com/lgh121546/221872278258 (2) DP 배열 정의 -> DP[idx] : idx까지 가장 긴 최장 증가 수열 2. Source Code #include #include #include #define MAXLEN 1000 using namespace std; /* 문제 .. 이전 1 2 다음
