[알고리즘/그리디] 21314번 : 민겸 - python

링크 : https://www.acmicpc.net/problem/21314

21314번: 민겸 수

 

---

• 문제
• 소요시간: 30분 max 부분 실패

---

• 설계하기(접근방법) 

1. 입력받기

 

2. 알고리즘 해석

 

규칙 1) 10^N 꼴의 십진수는 N + 1개의 M으로

1-> M

10 -> MM

100 -> MMM

 

규칙 2) 5 × 10^N 꼴은 마지막에 K를 붙여 5의 배수임을 나타낸다

 

M과 K의 조합에 따라 다양한 수가 나올 수 있는데 그 변수를 만드는 것은

 

MK로 이루어진 문자열에서 나타난다

 

MK를 함께 가면 50, M과 K를 따로 가져가면 15가 되기 때문에

 

가장 큰수를 만드는 방법은 모든 MK를 50으로 만드는 것

가장 작은 수를 만드는 방법은 모든 MK를 15로 만드는 것이다

 

구현방법)

최대 -> k가 나올때까지 1을 m(변수)에 더해간다

k가 나타나면 5 * 10^m을 곱해주고 max 문자열에 더해준다

 

최소 -> 10 ^ m을 곱해주고 5를 더한다.

만약 m이 0이상이 아니었다면 그냥 5를 더한다.

 

만약 끝이 m으로 이루어진 문자열이었다면

max는 1로 채우고

min는 ex) m = 3 일때 100으로 채운다

 

3) 출력하기

 

 

 

 

 

---

• 코드(출력)

import sys
input = sys.stdin.readline

s = input().rstrip() 

m = 0
max = ''
min = ''

for i in s:
    if i == 'M':
        m += 1
    else: # i가 k일 경우
        if m>0:
            max += str(5*(10**m))
            min += str(10**m + 5)
        else:
            max += '5'
            min += '5'
        m = 0

# 'M'으로 끝날 경우
if m>0:
    max += '1' * m
    min +=  str(10**(m-1))

print(max)
print(min)

출처 : https://yuna0125.tistory.com/44 님의 코드를 참고했다

---

• 얻어갈 부분

1. 논리를 다 해체하여 배열로 구현하려하다 실패했다. 풀이가 복잡해진다고 느끼면 다른 풀이방법을 생각해보자