![]()
1. 문제 풀이 동적계획법(dynamic_programming)을 사용하여 풀이하였습니다. 부분 문자열이 palindrome임을 확인하는 dp와 분할 개수의 최솟값을 구하는 dp로 두 번 나누어 진행하여 풀이하였습니다. 부분 문자열이 palindrome 확인 로직은 중앙값을 잡고 상태 유지 여부를 확인하면서 갱신하였습니다. 이때, palindrome의 길이가 짝수인 경우는 중앙값이 두 개 필요하므로 홀수, 짝수를 나누어서 갱신했습니다. 분할 개수를 확인하는 로직은 0, n-1 사이에 mid값을 counter로 문자열[0 : mid+1]이 palindrome이면 [mid+1 : en]에서 palindrome을 찾게 재귀로 구현하여 풀이했습니다. 2. 코드#include using namespace std;..
![]()
1. 문제 풀이 union-find를 통해 친구 관계를 이어주었다. 여기서 루트 값에 사탕의 개수를 넣어주었고, 각 집합의 인원수는 다른 배열에 저장하여 union을 진행했다. 이를 이용하여 knapsack dp를 사용하여 특정 집합의 인원을 표기해 주었다. knapsack 문제를 정말 오랜만에 풀어서 많이 헤매게 되었다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; ty..
