이번 문제는 백준의 골드 5 문제 홀수 홀릭 호석 문제이다.
문제를 차근차근 읽어보도록 하자.
어떤 수가 최대 10^9 - 1 까지 주어진다.
해당 수에서 홀수를 찾고, 세 자리 이상의 수라면 3등분한다.
3등분 한 수를 모두 합쳐 또 다른 수를 만들어 다시 홀수를 센다.
계속 반복하다, 한 자리만 남게되면 반복을 종료한다.
이 때 홀수의 최소 갯수와 최대 갯수를 반환해라!
문제 분석
먼저 문제의 조건을 한 번 분석해보자.
별다른 조건 없이 수의 최대값이 10^9 - 1 이란 조건 뿐이다.
10^9 - 1이란 말은, 수의 자릿수가 최대 9자리라는 말이 된다.
만약 단순 구현이라고 생각했을 때 9자리의 수를 계속 등분하는 경우의 수는?
매 순간순간 어디서 자르느냐에 따라 달라지게 된다.
가장 처음 3등분 하는 경우의 수는 8개의 칸막이 중 2개를 선택하는 것과 같다.
즉, 8C2이므로 28 가지 밖에 되지 않는다.
그 아래로 분할되는 경우 중 최악의 경우는 9 -> 8 -> 7과 같이 줄어드는 경우.
즉 28 * 21 * 15 * 10 * 6 * 3 * 1 정도 될 것이다.
계산해보면 약 1,500,000 정도 밖에 되지 않음을 알 수 있다!
따라서 그냥 구현으로 풀어봐도 될 것 같다는 생각이 든다!
구현
그럼 어떻게 구현할 것인지 생각해보자.
가장 먼저 떠오르는 것은 홀수를 세며 재귀함수를 통해 분할하는 것이다.
홀수 세기 -> 분할 -> 새로운 수 매개변수로 넘기기의 과정을 통해 구현해보자.
종료 조건으로는 문자열의 크기가 1일 때 멈추면 될 것이다.
최종적으로 아래와 같이 구현되었다.
int count_odd(string target){
int cnt = 0;
for (char digit : target)
if ((digit - '0') % 2 != 0)
cnt++;
return cnt;
}
void divide_num(string target, int curr_odd_cnt) {
curr_odd_cnt += count_odd(target);
int partition = 0;
if (target.size() >= 3) {
for (int i = 1; i < target.size() - 1; i++) {
for (int j = i + 1; j < target.size(); j++) {
partition = stoi(target.substr(0, i)) + stoi(target.substr(i, j - i)) + stoi(target.substr(j, num.size() - j));
divide_num(to_string(partition), curr_odd_cnt);
}
}
}
else if (target.size() == 2) {
partition = (target[0] - '0') + (target[1] - '0');
divide_num(to_string(partition), curr_odd_cnt);
}
else if (target.size() == 1) {
min_cnt = min(min_cnt, curr_odd_cnt);
max_cnt = max(max_cnt, curr_odd_cnt);
return; // 1자리가 되면 종료
}
}다행히도 한 번에 맞출 수 있었다!
생각보다 간단한 구현 문제였던 것 같다.
이것보다 깔끔하게 구현할 방법이 있을 것 같기도 하다.