알고리즘/BOJ
[BOJ] 2135번: String Compression
BaaaaaaaaaaaaaaaaaaaaaaarkingDog
2020. 12. 29. 12:00
보고 DP로 접근해야겠다는 생각이 쉽게 드는데, 일단 D[i][j]를 s[i:j]의 최소 길이라고 하겠습니다.
그러면 s[i:j] 구간은 어떤 적절한 부분문자열을 여러번 써서 만들어지거나(ex : abcabc=abc*2, gogogo=go*3), 아니면 중간에서 잘라 따로 따로 계산이 가능합니다.
즉 sep = i+1 to j에 대해 min(d[i][sep]+d[sep][j])를 계산하고
div = j-i의 진약수에 대해 min(2+d[st][st+div]+반복되는 횟수의 자리수)입니다. 2는 괄호 (와 )를 의미합니다. 코드를 참고해보세요.