문제 이해 단계
https://www.acmicpc.net/problem/20164
홀수개의 숫자가 입력으로 들어온다.
이때 숫자의 개수에 따라 다음에 규칙에 따른다.
숫자의 개수가 1개 -> 그대로
숫자의 개수 2개 -> 두 수를 더함
숫자의 개수 3개 이상 -> 임의의 지점에서 세 수를 나누어서 더함
위 행위를 숫자의 자릿수가 하나가 남을 때까지 반복한다.
이 과정에서 홀수가 총 몇 번 등장하는지를 세는 것인데,
숫자의 개수가 3개 이상일 때는
임의의 지점에서 나누기 때문에 여러 가지 경우의 수가 생긴다.
그래서 나올 수 있는 홀수의 최댓값과 최솟값을 구하는 문제이다.
문제 접근 단계
해당 문제에서의 핵심은 숫자의 개수가 3개 이상일 때
숫자를 3개의 분할로 나누는 것이다.
이걸 어떤 식으로 나눠야 할까?
그냥 이중 반복문으로 하나하나 다 탐색해서 해보면 될까?
사실 맞다.
이렇게 해도 되는 이유는 제한 사항 때문이다.
숫자 N의 범위가 10^9-1이기 때문에 최대 99999999까지이다.
이를 숫자가 아닌 배열로 살펴보면 그냥 8개의 배열에 불과하다.
즉 이중 반복을 해봤자 최대 8x8 이기 때문에
시간적으로는 충분하다. (브루트포스 가능)
그래서 경계를 나누는 방법은
그냥 모든 경우의 수를 다 나누어 보면서
최댓값과 최솟값을 다 구해보는 방법을 사용할 것이다.
다음으로 고민해봐야 하는 것은
해당 함수를 어떻게 구현하는 것이 편할까라는 것이다.
이 문제에서 조건을 보면 숫자가 1개일 때, 2개 일 때, 3개 이상일 때,
이런 식으로 숫자 개수를 기준으로 같은 행위가 반복된다.
그리고 나누어서 합해진 값을 또다시 분할하고
합하고 분할하고 합하고... 를 반복한다.
해당 경우에 따른 최솟값과 최댓값을 구하기 위해서는
재귀함수를 쓰는 게 적절하다고 생각했다.
해당 문제는 구현 문제이기 때문에
문제 구현 단계에서 코드와 함께 자세히 설명하겠다.
문제 구현 단계
#include <iostream>
#include <string>
#include <utility>
using namespace std;
// 나누고 합하는 재귀함수(숫자, 현재 카운트된 홀수 개수)
pair<int,int> solution(string num,int count){
int ansMax = 0;
int ansMin = 99999;
// 현재 숫자에서 홀수를 카운트
for(char iter : num) {
int val = iter - '0';
if(val % 2 != 0) count++;
}
// 숫자가 1개 일 때는 그냥 리턴
if(num.size() == 1) {
ansMin = ansMax = count;
return make_pair(ansMin,ansMax);
}
// 숫자가 2개 일 때는 두 수를 합해서 재귀함수 호출
else if(num.size() == 2){
int val = 0;
for(char iter : num) val += (iter-'0');
return solution(to_string(val),count);
}
// 숫자가 3개 이상일 때
else{
// 3등분할 수 있는 모든 경우의 수를 다 해줌
for(int i = 0; i < num.length()-2; i++){
for(int j = i+1; j < num.length()-1; j++){
string s1 = num.substr(0,i+1); // 0 ~ i 까지
string s2 = num.substr(i+1,j-i); //i+1 ~ j까지
string s3 = num.substr(j+1); // j ~ 끝 까지
string sum = to_string(stoi(s1) + stoi(s2) + stoi(s3));
// 합한 수로 다시 재귀함수 호출
pair<int,int> val = solution(sum,count);
// 최대 최솟값을 비교, 갱신
ansMin = min(ansMin,val.first);
ansMax = max(ansMax,val.second);
}
}
return make_pair(ansMin,ansMax);
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
string input;
cin >> input;
pair<int,int> answer = solution(input,0);
cout << answer.first << " " << answer.second;
}
solution 함수 부분이 재귀함수 부분으로
숫자의 개수별로 다르게 처리하는 역할을 한다.
함수 처음에는 현재 숫자에서 홀수를 뽑아내서 더하고,
개수를 기준으로 판단한다.
2개일 때는 두 숫자를 합하고,
그 합한 수로 다시 한번 함수를 호출하여 그 숫자의 홀수 개수를 판단한다.
3개 이상일 때는 3 등분해야 한다.
근데 어떤 경계로 잘라야 최댓값, 최솟값이 되는지 모르기 때문에
모든 경계에 대해서 함수를 호출하기 위해
이중반복문을 통해 각각 3 등분해 준다.
이렇게 하면 각기 다른 경우의 수에 따른 홀수의 개수가 리턴될 것이다.
이렇게 리턴된 값을 비교하여 max값과 min 값이 나올 것이고,
이 값들을 pair로 리턴한다.
사실 구현 문제는 말로 하는 것은 쉽지만
말 그대로 구현하는 것은 복잡하다.
특히 재귀 함수로 구성하였기 때문에 더 그러하다.
이 문제는 이렇게 이해만 하고 넘어가기보다는
직접 한번 풀어보는 것이 좋을 것 같다.
시행착오
재귀함수로 구성하다 보니 시간이 오래 걸렸다.
그 외에 부분에 대해서는 그렇게 어렵진 않았던 것 같은데,
이상하게 빠르게는 못 푸는 것 같다.
코딩테스트에서는 시간이 생명인데 좀 더 빠르게 푸는 연습이 필요할 것 같다.