개인공부용123 프로그래밍 블로그

문제 : https://algospot.com/judge/problem/read/DRAGON DP를 이용해서 드래곤 커브의 부분 문자열을 출력하는 문제입니다. 문제에서 드래곤 커브의 세대는 최대 50이므로 크기 50의 int 배열을 이용해서 DP로 구현했습니다. 부분문자의 시작부터 하나씩 문자를 출력해나가는 함수입니다. X나 Y를 N번 중첩한 길이를 length배열에 미리 저장해두고 불필요한 재귀를 줄여서 문제를 해결하면 됩니다.그리고 문자열의 시작위치는 1000000000을 넘을수 없으므로 만약 중첩길이가 1000000000을 넘으면 1000000000으로 설정하면 overflow를 예방할 수 있습니다. #include #include #include using namespace std; const i..

문제 : https://algospot.com/judge/problem/read/PI DP를 이용해서 최소비용으로 조각들을 설정하는 방법에 대해 다룬 문제입니다. 최소 3개에서 최대 5개의 부분조각을 가질수있으며 부분조각들의 패턴에 따라 비용이 결정되는 함수를 생성하고 cache배열에 최소비용을 저장하는 방식으로 dp를 이용해서 문제를 해결했습니다. 코딩을 하던중 책에서 string(temp.size(), temp[0]) 함수를 찾아서 이용했습니다. string(size_t c, char c)함수는 c를 n개 채우는 함수입니다. #include #include #include #include using namespace std; string N; const int INF = 987654321; int c..