![[레벨:4]](./modules/point/icons/default/4.gif "포인트:2035point (90%), 레벨:4/30"){kind=icon}
soyoja
Editorial 을 읽고 다른 사람들 풀이를 봐도 좀 알듯 말듯 하네요 -_-;
모든 경우를 다 돌리는 방법과 Greedy 로 푸는 방법이 있는 것 같은데, 푸신 분들 이 문제 해법 좀 자세히 설명 부탁드려요...
ps ) 요새 algospot 이 좀 침체? 된 느낌인데... 질문이라도 열심히 올리겠슴다.. ㅋㅋ
Editorial 을 읽고 다른 사람들 풀이를 봐도 좀 알듯 말듯 하네요 -_-;
모든 경우를 다 돌리는 방법과 Greedy 로 푸는 방법이 있는 것 같은데, 푸신 분들 이 문제 해법 좀 자세히 설명 부탁드려요...
ps ) 요새 algospot 이 좀 침체? 된 느낌인데... 질문이라도 열심히 올리겠슴다.. ㅋㅋ
![[레벨:1]](./modules/point/icons/default/1.gif "포인트:135point (37%), 레벨:1/30"){kind=icon}
Neon
제맘대로 설명을 하자면... 먼저 'a'~'z'의 갯수를 세서 배열에 저장합니다. 이제 roughness는 cnt 배열 중 가장 큰 값 - cnt 배열 중 0보다 크면서 가장 작은 값이 될텐데, 우리가 개입할 수 있는 건 cnt 배열의 각 element를 n개까지 맘대로 뺄 수 있습니다.
roughness를 최소화 하기 위해서는 cnt 배열 중 가장 큰 값을 줄이거나, cnt배열 중 0보다 크면서 가장 작은 값을 키우는 방법이 있는데, 이 비용이 n보다 작으면서 가장 roughness를 최소화할 수 있는 방법을 찾으면 됩니다.