[백준][C++] 21314 민겸 수

21314. 민겸 수

21314번: 민겸 수

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

민겸 수를 10진수로 바꿨을 때 가장 큰 값과 가장 작은 값을 출력하는 것. 민겸아, 참으로도 요상한 짓을 했구나.

 

처음엔 어려워 보였지만, 생각보다 간단한 문제였다. 예제를 보면 알 수 있다.

최댓값은 505500, 최솟값은 155105, 최댓값과 최솟값이 나온 알고리즘을 따라가보고 최댓값을 구할 때, 최솟값을 구할 때의 규칙을 정의해보았다.

 

 

알고리즘 설계

1. 일단 최댓값은 M과 K가 붙어있다면 절대 따로 계산하지 않는다.

input =>
MMMMMK

output =>
// 따로 계산한다면... 
111115
100005

// 같이 계산한다면... (10^M의 개수  * 5)
500000

 

앞자리부터가 1에서 5로 달라지니, 10^M의 개수 * 5 꼴로 계산해야 한다.

 

2. 마지막 남은 M은 모두 1로 처리한다.

 

input => MMMKMMM

// 1대로 한다면

output =>
5000...

// M을 K와 처리할 수 없으니 경우의 수를 구해보자
5000100
5000101
5000111

이렇게 남은 M을 모두 1로 처리하는 것이

일의자리, 십의 자리, 백의 자리... 등에 있는 수를 0에서 1로 올려주게 된다.

 

이 규칙을 기반으로 최댓값을 구하는 코드를 짜보았다.

string max = "", number;
int mCount = 0;
cin >> number;

// MAX
for (int i = 0; i < number.size(); i++)
{
    if (number[i] == 'M') mCount++;

    else
    {
        // K는 5 * 10^(mCount)로 계산
        max.push_back('5');

        if (mCount > 0)
        {
            for (int j = 0; j < mCount; j++)
                max.push_back('0');

            mCount = 0;
        }
    }
}

// 남은 M 처리
for (int j = 0; j < mCount; j++)
{
    // MAX는 모두 1로 계산 
    max.push_back('1');
}

 

최솟값은...

 

1. M은 혼자 계산하거나, M이 여러개이면 10^(M 개수) 형태로 M끼리만 계산한다.

input =>
MKMMK

output =>
// M을 K와 계산했을 때
50500

// 1대로 계산했을 때
15105

이렇게 계산하게 되면, 50, 500으로 계산하게 될 것을 15, 105로 줄일 수 있다.

 

2. 남은 M도 위와 같이 계산한다.위와 같은 형식으로 계산하면, 일의자리, 십의자리 등등을 1에서 0으로 줄일 수 있다.

 

input =>
MKMMM

output =>
15100
15110
15111

 

이를 구현해본 최솟값을 구하는 코드이다.

string min = "", number;
int mCount = 0;
cin >> number;

// MIN
for (int i = 0; i < number.size(); i++)
{
    if (number[i] == 'M') mCount++;

    else
    {
        if (mCount > 0)
        {
            for (int j = 0; j < mCount; j++)
            {
                // MIN은 1이나 10^(mCount)로 계산 후
                if (j == 0)
                    min.push_back('1');
                else
                    min.push_back('0');
            }

            mCount = 0;
        }

        // MIN은 M 따로 K 따로
        min.push_back('5');
    }
}

// 남은 M 처리
for (int j = 0; j < mCount; j++)
{
    // MIN은 1이나 10^(mCount)로 계산
    if (j == 0)
        min.push_back('1');
    else
        min.push_back('0');
}

 

코드

#include<iostream>
#include<string>
#include<math.h>
using namespace std;

int main()
{
	string max = "", min = "", number;
	int mCount = 0;
	cin >> number;

	for (int i = 0; i < number.size(); i++)
	{
		if (number[i] == 'M') mCount++;

		else
		{
			// MAX는 5 * 10^(mCount)로 계산 
			max.push_back('5');

			if (mCount > 0)
			{
				for (int j = 0; j < mCount; j++)
				{
					// MIN은 1이나 10^(mCount)로 계산 후
					if (j == 0)
						min.push_back('1');
					else
						min.push_back('0');

					max.push_back('0');
				}

				mCount = 0;
			}

			// MIN은 M 따로 K 따로
			min.push_back('5');
		}
	}

	// 남은 M 처리
	for (int j = 0; j < mCount; j++)
	{
		// MIN은 1이나 10^(mCount)로 계산
		if (j == 0)
			min.push_back('1');
		else
			min.push_back('0');

		// MAX는 모두 1로 계산 
		max.push_back('1');
	}

	cout << max << endl << min;
}

 

최종 구현 코드는 위 두 코드를 합쳐놔서 가독성이 조금 떨어지긴 한다만... 그래도 잘 풀어낸 것 같아서 기분이 좋다.

 

민겸... 다음엔 더 어려운 민겸수2를 만들어 와라...