Approach path(y, x) : (y, x)ㄱ에서 시작해서 맨 아래줄까지 재려가는 부분 경로의 최대합 이렇게 정의했을 경우, path(y, x)는 y ~ n - 1까지의 아직 해결하지 못한 조각들에 대한 값을 정의하는 부분이므로 이전 입력값에 영향을 받지 않는다. 즉, (y, x)까지 어떤 경로로 도착했건 남은 부분 문제는 항상 최적으로 풀어도 상관이 없다. 이러한 성질을 최적 부분 구조(Optimal substructure)이라고 한다. 이러한 성질 때문에 지금까지의 선택과 관계 없이 각 부분 문제를 최적으로 풀기만 하면 전체 문제의 최적해도 알 수 있게 되는 것이다. 따라서 탑-다운 방식으로 이 문제를 해결할 수 있게 된다. Code #include #define fastio ios_base:..

Approach *에 몇 글자가 대응하는지 여부가 가장 중요하다. 이 문제를 완전탐색을 통해서 해결할 수 있다. 완전탐색을 통해 해결할 수 있으나, 문자열의 길이가 100자리 이하라는 것을 감안할 때 비둘기집 원리를 이용하면 총 101 * 101 가지 이하만 계산해주면 된다는 것을 이해할 수 있다. (즉, 중복되는 계산이 무조건적으로 생기므로 메모이제이션을 활용하면 중복되는 계산을 줄일 수 있다.) Code 1. $0(N^3)$로 푸는 풀이 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; string W; string T; int dp[101][101]; int memoizat..

상당히 교훈적인 문제이다. 이 문제는 입력 숫자가 작은 편이므로 Bruteforce 방법을 먼저 생각하는 것이 압도적으로 유리하다. 다만, 이 문제를 풀 때 가장 애를 먹은 사항이 중복되지 않으면서 채워나가는 것이다. 앞의 6.2장 피크닉 문제에서의 교훈인 "중복을 피하기 위해서 가장 좋은 방법이 가장 왼쪽 상단 index를 기준으로 하는 것이다"을 활용하여 조금씩 채워나가면 된다. 기본적인 문제 풀이의 방향성은 다음과 같다. 1. 비어있는 가장 왼쪽 상단 cordinate를 찾는다. 2. 해당 cordinate를 덮을 수 있는 블록을 찾는다.(이 과정에서 블록이 외부로 넘어가는지 여부를 체크한다.) 3. 해당 블록을 덮었다고 가정하고 이후의 과정을 반복한다. (재귀를 활용해서 이를 구현하되, 각 단계가..

문제 자체는 어렵지 않은 편이다. 친구인 학생들끼리만 짝을 지어주어야 하므로 입력받은 짝을 순차적으로 Brute-force방법을 활용하여 탐색해주면 된다. #include #include #include using namespace std; int student_num, friend_pair_num; int result = 0; void group_maker(vector &friend_store, vector &pair_store, int check_num, int index){ // 확인하는 케이스(총 member수가 구해야하는 것과 같을 때 전체 케이스를 만족하는지 체크) if(check_num == 0){ vector check_value(student_num, 0); for(int i = 0; i..