반응형 팰린드롬2 [C/C++] 백준 #1747 소수&팰린드롬(수학) 이번 문제는 n 이상의 수중에 가장 작은 소수이면서 팰린드롬이 되는 수를 찾는 문제입니다. 구현을 위한 핵심은 다음과 같습니다. 1) n의 앞부분 절반의 수를 구합니다. 예를 들어서 120의 경우라면 3자리 숫자에 12가 됩니다. 31과 같은 숫자는 2자리 수에 3이 됩니다. 2) 절반의 수를 이용해서 같은 자리수의 팰린드롬을 구합니다. 120의 경우에는 121이 팰린드롬 수가 됩니다. 31의 경우에는 33이 팰린드롬이 됩니다. 이 수가 n 이상의 수가 된다면, 통과이고, 그렇지 않다면 절반의 수에 1을 더합니다. 이 수는 반드시 n보다 큰 수가 되기 때문에 1을 더하는 것으로 충분합니다. 3) 그 수부터 시작해서 팰린드롬이 되는 수 중에 소수인 수를 찾습니다. 여기서 사실 알고리즘 효율을 위해서 맨 첫.. 2022. 10. 9. #1509 팰린드롬 분할 팰린드롬 분할은 주어진 문자열에 팰린드롬이 되는 단어들로 나눌 때 나오는 팰린드롬의 개수가 최소가 되는 수를 계산합니다. 맞힌 사람들의 수행시간을 보니, 제 알고리즘은 그다지 좋지는 않습니다. 제 알고리즘은 \(O(N^3)\)인데, 이보다 적게 계산할 수 있는 방법이 있겠죠. 일단 기본적인 생각은 앞에서부터 n개의 글자에 대한 팰린드롬 분할의 최소 개수를 구합니다. 이것을 \(dp_n\)이라고 한다면, 1개의 글자는 그 자체로 팰린드롬이니, \[ dp_0 = 0, dp_1 = 1 \] 이 됩니다. \[ dp_{n+1} = min_{i = 0,...,n-1}(dp_{i} + 1~ if~ s[i:n]~is~pallindrome) \] 이 방식대로 구현한 프로그램은 아래와 같습니다. 좀 더 효율적인 프로그램을.. 2022. 8. 22. 이전 1 다음 728x90
