[BOJ] 2135번: String Compression

www.acmicpc.net/problem/2135

 

보고 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는 괄호 (와 )를 의미합니다. 코드를 참고해보세요.

 

github.com/encrypted-def/BOJ/blob/master/2135.py

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 2135번: String Compression  (3) 2020.12.29
[BOJ] 19235번: 모노미노도미노  (2) 2020.10.10
[BOJ] 4889번: Seinfeld  (0) 2020.03.19
[BOJ] 3078번: MALCOLM  (0) 2020.02.28
[BOJ] 14862번: 최대공약수 기댓값  (4) 2020.02.28
[BOJ] 16409번: Coprime Integers  (0) 2020.02.25
[BOJ] 8291번: Coprime Numbers  (0) 2020.02.25
  Comments
댓글 쓰기