아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

아름다운 전화번호

면접 대비

시간 제한2초메모리 제한1024 MB

요약
7자리 전화번호를 2~4자리 묶음으로 하이픈으로 나누어 패턴 점수 합이 최대가 되게 하고, 가장 아름다운 분할과 그 점수를 출력한다.
난이도

보통10점 중 6점

유형
동적 계획법, 문자열, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

여러 회사가 기억하기 쉬운 <<아름다운>> 전화번호를 광고에 사용한다는 사실을 눈치챘을 것이다. 그런데 회사 전화번호가 별로 특별하지 않다면 어떻게 해야 할까? 번호를 잘 살펴보고 숫자를 재배열하면 훨씬 아름다워질 수도 있다. 예를 들어 회사 번호가 872-73-33이라면 숫자를 8727-333처럼 재배열해서 더 아름답게 만들 수 있다.

전화번호를 나누는 방식의 아름다움을 다음과 같이 평가한다. 번호를 하이픈으로 나누어 2자리에서 4자리까지의 그룹으로 만든다. 이때 나눈 방식의 아름다움은 각 그룹이 주는 점수의 합이다. 점수는 다음 표로 계산한다.

그룹 패턴점수
aa2
aba2
aab, abb2
aaa3
abac, baca2
abab3
aabb3
abba4
baaa, abaa, aaba, aaab3
aaaa5

이 표에서 기호 <>, <>, <>는 서로 다른 숫자를 나타낸다. 예를 들어 패턴 <>에는 그룹 <<223>>, <<667>>이 해당하지만 <<123>>과 <<888>>은 해당하지 않는다.

이 평가 기준으로 주어진 번호의 가장 아름다운 분할을 찾아라.

입력

입력 파일에는 7자리 숫자로 이루어진 한 줄이 주어진다. 이는 주어진 전화번호이다.

출력

출력 파일의 첫째 줄에 가장 아름다운 분할을 출력하고, 둘째 줄에 그 아름다움의 값을 출력한다.

아름다움의 값이 최대인 분할이 여러 개라면 그중 아무거나 하나를 출력한다.

예제2

  1. 예제 1

    입력
    8727333
    
    예상 출력
    8727-333
    5
    
  2. 예제 2

    입력
    8827291
    
    예상 출력
    88-272-91
    4