PermRLE > 문제은행

본문 바로가기


문제은행

1026 : PermRLE

제한시간: 5000 ms    메모리제한: 128 MB
해결횟수: 7 회    시도횟수: 35 회   



당신은 Run-Length Encoding을 조금 더 개량하여 PermRLE라는 이름의 알고리즘을 만들었다.

 

PermRLE란 어떤 문자열 S가 있을 때 임의의 자연수 K와 1 ~ K로 이루어진 순열을 생성하고 문자열을 K개씩의 구간으로 쪼개서 임의로 배열한 다음 이를 압축하는 알고리즘이다. 예를 들어 S = "abcdefghijkl"이고 K = 4 {3, 1, 4, 2} 라는 순열이 있으면 우선 이 문자열을 4개씩으로 묶어서 쪼개면 "abcd / efgh / ijkl"가 된다. 이를 {3, 1, 4, 2} 순서로 배열한다. 즉 세 번째 위치에 있는 c가 제일 처음에 첫 번째 위치의 a가 가 그 뒤에 마찬가지로 네 번째 위치와 두 번째 위치의 d b가 순서대로 배열되는 것이다. 쪼갠 조각들에 대하여 같은 과정을 반복하면 "cadb / gehf / kilj" 가 되는 것이다.

 

이렇게 재배치한 문자열이 있을 때 PermRLE에서는 같은 문자열을 하나로 묶어서 표현한다. "aaabcaa" 라는 문자열이 있으면 "aaa" "b" "c" "aa"로 묶어서 길이 4짜리 문자열이 된다.

 

어떤 String S와 K가 주어지면 생성된 순열에 따라 PermRLE로 압축한 결과가 다르다는 것을 깨달았다. 순열을 임의로 생성할 수 있다고 할 때 PermRLE로 만들 수 있는 압축된 문자열의 최소 길이를 구하는 프로그램을 작성하시오.


입력의 첫 번째 줄에는 숫자 K가 입력된다. K는 2 이상 16 이하이다. 두 번째 줄에는 압축을 하고자 하는 문자열이 입력된다. 문자열의 길이는 50,000 이하이다. 입력 데이터들의 40%는 K가 4이하이고 문자열의 길이가 1,000 이하인 입력데이터이다.



입력에 대해서 압축된 문자열의 최소 길이를 출력하는 프로그램을 작성하라.


[Copy]
4
abcabcabcabc
[Copy]
7


출처 : GCJ 2008 R2


GCJ 2008 R2 D_PermRLE

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.