공부중의 블로그

Examples : Input : VOLVO Output : 3 Explanation : (VO)L(VO) Input : merchant Output : 1 Explanation : No chunks possible. Input : ghiabcdefhelloadamhelloabcdefghi Output : 7 Explanation : (ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi) ------------------최악의 경우(abcde) 1 개는 보장된다.최선의 경우abcba >> n개가 보장azcba >> 3개(a)(zcb)(a)일단 팰린드롬인 애는 그대로 포장할 수 있다. 포장해도 되는 애를 안해서 얻는 이득이 있나?팰린드롬인 단어를 포장하지 않는 경우 갯수가 무조..

우선 "최소"를 물어본데다, 최적해가 없어 보이고(자료구조해도), DP가 될 것 같아 보이니까 완전탐색에서 시작해서 DP로 캐핑해보자.그냥 완전탐색을 생각해 보면, 본인보다 작은 모든 완전제곱수를 1 ~ 최대 갯수만큼 채우면서 재귀를 돌려보자. int findmin(int n, int curr, int total){if(curr==0) return 0;int ret = INT_MAX;for(int i = 0 ; curr*i> O(N^2) 알고리즘 쯤 될듯.

진짜 멍청한 조합탐색(정말 순서 없이는 절대 풀 수가 없어서 - 폭탄이 터진다던가 - 결국에는 순서를 전부 기록해야 결과 확인이 가능한 경우)고른다. 마지막에서 계산한다. 확인한다. 여기에서 더 발전시킬 수 없을까? "마지막에 하는 작업을 분산시킬 수 있나"마지막에 뭘 하는데? 합을 구한다. 그러면 합을 단계별로 구할 수 있잖아? 당연하지. 그러면 현재까지의 합을 인자로 넘겨가며 계산한다. 어 인자가 두개네, curr, sum >> DP capping이 가능해진다.게다가, sum = total/2 면 자동으로 종료가능하다..!! (참고로 이 문제는 knapsack와 유사한 DP다) bool canfind(vector & data, int curr, int total, int sum){if(total>su..

차이값을 주어진 값 이하로 맞추면서, 원래 배열에서 최소 한도로 움직이도록 해야 한다. 그 바꾼 값을 반환하자. ex )[1,4,2,3]target = 1;>> ans :[2,3,2,3]바꾼 양 : 2 >>> ans = 2 ** 솔직히 이 문제는 "최적 값을 구하시오" 그리고 "숫자 상한이 100이다" 에서 - 아 이 문제는 DP구나 가 바로 떠올라서 완전 탐색으로 넘어갈 생각을 했어야 한다. 뭐 그리디 한두번은 해볼 수 있었겠지만 안정적으로 DP를 해놓고 찾았을꺼다. ** 솔루션 : 그리디 솔루션 : 한쪽 끝에서부터 생각해 보자. 한도 내로 맞추기 위해서 1을 움직일까 4를 움직일까?아님 중간으로 맞출까?일단 움직이는 총량은 같다. 어찌됬든, 차이를 그렇게 만들어야 하기 때문. 그럼 그 다음 값이 무엇..