[알고리즘 풀이 분석] BOJ 20164 홀수 홀릭 호석

면접 + 코테 의 폭풍같은 일주일을 보내고,, 보상심리 겁나 올라와서 탱자탱자 3일 놀았다 ㅎㅎ 다음주 토욜 중요한 코테를 위해 다시 열심히 풀어보기 위해 오늘은 웜업으로 BOJ 20164 홀수 홀릭 호석를 풀어보았다. 골드 5단계 문제이고 구현 문제이지만 경우의 수와 문자열을 다룰 줄 안다면 쉽게 풀 수 있는 문제였다.

(다만 문제 설명이 좀 이상하다,, 구하라는게 정확히 나와있지 않아서 다시 읽어봐야했다,,)

BOJ 20164 홀수 홀릭 호석

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

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

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

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

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

입출력

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

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

• 1 ≤ N ≤ 109-1, N 은 자연수이다.

나의 풀이

먼저 재귀적으로 구현하였고 입력을 string 으로 받아 바로 바로 길이를 확인할 수 있도록 하였다.

길이가 1일 때 재귀가 종료되고 2일때 혹은 3 이상이면 주어진 규칙대로 연산을 수행한다.

문자열의 원소를 index 로 접근하면서 아스키 코드값을 활용해 홀수의 갯수를 세어주고 재귀함수의 매개변수로 넘기면서 재귀 종료시 최대, 최소 값을 갱신하였다.

길이가 3이상일 때는 0을 제외한 나머지 문자열 인덱스 위치 중 2가지를 더 고르는 경우의 수를 이용해 재귀 함수를 호출하였다.

재귀, 문자열, 경우의 수 를 다룰 줄 안다면 쉽게 해결할 수 있는 문제인 것 같다. 코테 1번, 2번으로 나올법한 난이도가 아닐까!

코드

#include <iostream>
#include <string>
#include <limits.h>
#include <vector>
#include <algorithm>

// boj 20164 홀수 홀릭 호석, 골드 5, 구현
using namespace std;

int MAX = -1;
int MIN = INT_MAX;

vector<vector<int>> makeIndexes(int len){
    vector<vector<int>> result;

    vector<bool> select(len-2, false);
    for (int i = 0; i < 2; ++i) select.push_back(true);

    do{
        vector<int> combi;
        for (int i = 0; i < len; ++i) {
            if (select[i]) combi.push_back(i+1);
        }
        result.push_back(combi);
    }while (next_permutation(select.begin(), select.end()));

    return result;
}

void solution(string N, int count){
    if (N.size() == 1){
        if ((N[0]-'0')%2 == 1) count++;
        if (MIN > count) MIN = count;
        if (MAX < count) MAX = count;
        return;
    }

    if (N.size() == 2){
        char front = N[0], back = N[1];

        if ((front -'0') % 2 == 1) count++;
        if ((back -'0') % 2 == 1) count++;

        int sum = stoi(N.substr(0,1)) + stoi(N.substr(1,1));
        solution(to_string(sum), count);
        return;
    }

    int len = N.size();
    for (int i = 0; i < len ; ++i) {
        if ((N[i]-'0')%2 == 1) count++;
    }
    vector<vector<int>> index_combination = makeIndexes(len-1);
    for (int i = 0; i < index_combination.size(); ++i) {
        int first = stoi(N.substr(0,index_combination[i][0]));
        int mid = stoi(N.substr(index_combination[i][0], index_combination[i][1]-index_combination[i][0]));
        int last = stoi(N.substr(index_combination[i][1], len-index_combination[i][1]));
        string str_sum = to_string(first+mid+last);
        solution(str_sum, count);
    }
}


int main() {
    string N;
    cin>>N;

    solution(N, 0);

    cout<<MIN<<" "<<MAX;

    return 0;
}