[백준 20164] - 홀수 홀릭 호석(C++)[골드5]

문제

호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 홀수 홀릭에 빠진 호석이는 가지고 있는 수 N을 일련의 연산을 거치면서, 등장하는 숫자들에서 홀수를 최대한 많이 많이 보고 싶다.

하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다.

• 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.
• 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.
• 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.
• 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.

호석이는 연산이 종료된 순간에 종이에 적힌 수들을 모두 더한다. 그렇게 최종적으로 얻은 수를 최종값이라고 하자. 예를 들어, 시작하는 수가 82019라고 하자. 그럼 아래와 같이 나누게 되면 5개의 홀수를 볼 수 있기 때문에, 최종값이 5가 된다.

시작할 때 호석이가 가진 수를 N 이라고 했을 때, 만들 수 있는 최종값 중 최솟값과 최댓값을 구해주자.

입력

첫번째 줄에 호석이가 처음 시작할 때 가지고 있는 수 N 이 주어진다.

출력

첫 번째 줄에 호석이가 만들 수 있는 최종값 중에서 최솟값과 최댓값을 순서대로 공백으로 구분하여 출력한다.

 

🔎문제 해석

이러한 구현 문제는 특정 알고리즘을 요구하는 것이 아닌 문제에서 필요한 알고리즘을 사용하는 문제입니다.
따라서 문제에서 요구하는 바를 이해하고 차례대로 진행하면 쉽게 풀 수 있는 문제입니다.
우선 문제에서 가장 주의 깊게 봐야 할 점은 숫자가 3자리 이상일 때 쪼개는 경우의 수를 잘 생각해줘야 합니다.
저는 입력받은 숫자의 크기가 10^9-1이라는 점을 참고해서 푸르트 포스 알고리즘을 이용해서 경우의 수를 특정해 줬습니다.

 

💡문제 풀이

1. 연산의 순서대로 설명을 하겠습니다.
   1. 숫자에서 각 홀수의 개수를 더해줍니다.
   2. 이다음 연산은 숫자의 자릿수에 따라 달라집니다.
      • 숫자가 한자리일 때 : 더 이상 연산을 진행하지 않고, 종료합니다.
      • 숫자가 2자리일 때 : 두 자리의 숫자를 합해서 새로운 숫자를 만들고 1번 연산을 다시 진행합니다.
      • 숫자가 3자리 이상일 때 : 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개의 수를 더해서 새로운 숫자를 만든 뒤
        1번 연산을 다시 진행합니다.
2. 연산이 종료되면 우리는 연산동안 홀수의 개수를 기록해야 합니다.
   1. 더 자세하게는 최솟값과 최댓값을 기록해줘야 합니다.

 

💡함수 설명

함수는 크게 3가지를 사용했습니다.

 

해당 숫자에서 홀 수를 더해주는 함수

int findnum(string n){
    int temp = 0;
    int tempans = 0;
    for (int i = 0; i < n.size(); i++)
    {
        temp = n[i] - '0';
        if (temp % 2 != 0) // 홀수면
        {
            tempans++;
        }
    }
    return tempans;
}

숫자가 두 자리일 때 두 숫자를 더해주는 함수

string addnum(string n) //두 자리면 두개 더하는 함수.
{ 
    int tempnum = 0;
    for (int i = 0; i < n.size(); i++)
    {
        tempnum += n[i] - '0';
    }
    return to_string(tempnum);
}

재귀함수

void funct(string number, int total)
{
    if (number.length() == 1) //수가 한자리 일 때
    {
        total += findnum(number);
        answer = max(answer, total); //최대값 저장
        small = min(small, total); //최소값 저장
        return;
    }
    else if (number.length() == 2) //숫자가 2자리 일 때
    {
        total += findnum(number);
        funct(addnum(number), total); // 두 자리를 더한 숫자를 temp에 넣어줌.
    }
    else if (number.length() >= 3) //숫자가 3자리 이상일 때
    {
        total += findnum(number);
        // 3자리를 쪼개야함.
        for (int i = 1; i < number.length() - 1; i++)
        {
            string first, second, third;
            for (int j = i + 1; j < number.length(); j++)
            {
                first = number.substr(0, i);                  
                second = number.substr(i, j - i);             
                third = number.substr(j, number.length() - j);
                int num = stoi(first) + stoi(second) + stoi(third);
                funct(to_string(num), total); // 세 개를 더한 수를 새로운 문자열로 탐색시작
            }
        }
    }
}

함수들은 주석을 달아놨기 때문에 설명은 생략하겠습니다!

 

💻전체 코드

/*
규칙
1 : 숫자에서 홀수의 개수를 종이에 적는다.
2 : 수가 한자리면 종료
3 : 수가 두자리면 두 자리 합쳐서 새로운 수를 만듬.
4 : 수가 세자리 이상이면 임의의 숫자 위치에서 3개 끊어서 분할하고, 3개를 더한 값을 새로운 수로 생각*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits.h>
using namespace std;
string str;
int answer = 0, small = INT_MAX;
int findnum(string n);
string addnum(string n);
void funct(string number, int total);
int main()
{
    cin >> str;
    funct(str, 0);
    cout<<small<<" "<<answer<<endl;
}
void funct(string number, int total)
{
    if (number.length() == 1) //수가 한자리 일 때
    {
        total += findnum(number);
        answer = max(answer, total); //최대값 저장
        small = min(small, total); //최소값 저장
        return;
    }
    else if (number.length() == 2) //숫자가 2자리 일 때
    {
        total += findnum(number);
        funct(addnum(number), total); // 두 자리를 더한 숫자를 temp에 넣어줌.
    }
    else if (number.length() >= 3) //숫자가 3자리 이상일 때
    {
        total += findnum(number);
        // 3자리를 쪼개야함.
        for (int i = 1; i < number.length() - 1; i++)
        {
            string first, second, third;
            for (int j = i + 1; j < number.length(); j++)
            {
                first = number.substr(0, i);                   // 0~i까지 짜르기.
                second = number.substr(i, j - i);              // i~ i+j-i
                third = number.substr(j, number.length() - j); // j~ 끝까지.
                int num = stoi(first) + stoi(second) + stoi(third);
                funct(to_string(num), total); // 세 개를 더한 수를 새로운 문자열로 탐색시작
            }
        }
    }
}
int findnum(string n){
    int temp = 0;
    int tempans = 0;
    for (int i = 0; i < n.size(); i++)
    {
        temp = n[i] - '0';
        if (temp % 2 != 0) // 홀수면
        {
            tempans++;
        }
    }
    return tempans;
}
string addnum(string n) //두 자리면 두개 더하는 함수.
{ 
    int tempnum = 0;
    for (int i = 0; i < n.size(); i++)
    {
        tempnum += n[i] - '0';
    }
    return to_string(tempnum);
}

 

😀느낀 점

• 구현문제는 문제를 이해하는데 굉장히 시간이 걸린다.. 내 독해력이 문젠가!!!? 슬프다.
• 문제를 이해하면 알고리즘은 어렵지 않다.