[Python/파이썬] 백준 21314번 민겸 수

21314번: 민겸 수

 

문제

민겸이는 로마 숫자를 보고 굉장히 흥미롭다고 생각했다. 그래서 민겸이는 새로운 수 체계인 민겸 수를 창조했다.

민겸 숫자는 0 이상의 정수 N에 대해 10N 또는 5 × 10N 꼴의 십진수를 대문자 M과 K로 이루어진 문자열로 표기한다. 10N 꼴의 십진수는 N + 1개의 M으로, 5 × 10N 꼴의 십진수는 N개의 M 뒤에 1개의 K를 이어붙인 문자열로 나타낸다. 즉, 아래 표처럼 나타낼 수 있다.

변환 전	변환 후
1	M
5	K
10	MM
50	MK
100	MMM
500	MMK
1000	MMMM
5000	MMMK
...	...

민겸 수는 한 개 이상의 민겸 숫자를 이어붙여 만든다. 예를 들어, 민겸 수 MKKMMK는 MK, K, MMK의 세 민겸 숫자를 이어붙여 만들 수 있다.

민겸 수를 십진수로 변환할 때는, 1개 이상의 민겸 숫자로 문자열을 분리한 뒤, 각각의 민겸 숫자를 십진수로 변환해서 순서대로 이어붙이면 된다. 민겸 숫자를 십진수로 변환하는 것은 십진수를 민겸 숫자로 변환하는 과정을 거꾸로 하면 된다. 예를 들어, 민겸 수 MKKMMK는 아래 그림과 같이 여러 가지 십진수로 변환할 수 있다.

민겸이는 위와 같이 하나의 민겸 수가 다양한 십진수로 변환될 수 있다는 사실을 알았다. 문득 민겸이는 변환될 수 있는 십진수 중 가장 큰 값과 가장 작은 값이 궁금해졌다. 민겸이를 위해 하나의 민겸 수가 십진수로 변환되었을 때 가질 수 있는 최댓값과 최솟값을 구해주자.

입력

민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다.

출력

주어진 민겸 수가 십진수로 변환되었을 때 가질 수 있는 값 중 가장 큰 값과 가장 작은 값을 두 줄로 나누어 출력한다.

코드

mg = input()

max_v, min_v = '', ''
m = 0
for i in range(len(mg)):
    if mg[i] == 'M':
        m += 1
    elif mg[i] == 'K':
        if m > 0:
            max_v += str(5*(10**m))
            min_v += str(10**m+5)
        else:
            max_v += '5'
            min_v += '5'
        m = 0

# 끝부분이 M으로 끝나는 경우
if m > 0:
    for i in range(m):
        max_v += '1'
    min_v += str(10**(m-1))
    
print(max_v)
print(min_v)

 

처음에는 DP 문제인줄 알고 DP 배열에 민겸 수 i번째 배열까지의 최대값, 최소값을 넣어서 계산하려 하였다. 근데 너무 복잡해져서 도저히 아닌거 같아서 알고리즘 분류를 보니까 그리디, 구현 문제인걸 알았다...

 

그래서 다시 푼 코드가 위의 코드이다.

 

입력으로 받은 민겸 수의 i번째 인덱스의 값이

1. 'M'일 때 : 'M'의 개수를 세기 위한 변수 m의 값 1 증가
2. 'K'일 때 
   • 앞에 'M'이 있었다면 최대값은 가능한 가장 앞의 값이 5로 바뀔 때의 값, 즉 가능한 가장 큰 덩어리로 민겸 수를 만들어 줄 때이고, 최소값은 현재 인덱스 'K'만 떼어내고 앞의 M들이 하나의 민겸 수로 볼 때이다. 예를 들어 MMK가 있다면 이 민겸 수는 500(MMK), 115(M,M,K), 105(MM,K)가 가능하다. 
   • 앞에 'K'가 있었다면 이 경우는 5를 덧붙이는 것만 가능하다.
   • 그리고 m의 값을 다시 0으로 초기화해준다.

주어진 민겸 수의 끝부분이 'M'으로 끝난다면 계산이 다 되지 않을 수 있기 때문에 마지막에 m이 0보다 큰 지 확인하여 처리해주는 과정이 필요하다.