[백준 20164][💛5] 홀수 홀릭 호석

🚀 난이도

💛 골드 5

🚀 문제

https://www.acmicpc.net/problem/20164

홀수에 미친 호석이

🚀 내 풀이 ⭕

재귀적으로 다음 과정을 수행하면 된다.

• 현재의 문자열 길이가 3 이상이라면 👉 문자열 길이를 세 부분으로 나누어 홀수 개수를 세고 합친다.(합친건 다음 재귀 문자열이 된다.)
  1. 문자열 길이를 S 라고 한다면 S-1 C 2 개의 조합을 구한다.
     • 예를 들어 “82019” 라면, 이 문자열을 3 개의 부분으로 나누기 위해선 “8💓2💓0💓1💓9” 이렇게 4 개의 💓 에서 2 개를 뽑는 것이라고 생각할 수 있다. 즉, 문자열을 나눌 수 있는 사이사이 부분은 항상 S-1개가 있는데 이 중에서 2 개를 뽑아 이 위치를 기준으로 substr를 통해 문자열을 3 개로 쪼갤 수 있는 것이다.
     • 임의로 세 파트로 나눈다고 하였으니 현재의 문자열 길이를 기준으로 S-1 C 2 조합을 모두 구한 후 하나하나 재귀 돌리면 된다.
     • N은 입력 크기가 아주 크나 이 N 의 길이 S 는 10 을 넘지 않으므로 시간 복잡도는 걱정하지 않아도 된다.
  2. 세 파트로 나눈 문자열 각각에서 홀수 개수를 구한다.
     • check_odd 함수를 만들어 이 함수에서 처리하도로 하였다.
  3. 문자열을 정수로 변환하여 합한 후 이를 다시 문자열로 변환하여 다음 재귀에서의 현재 문자열이 되도록 한다.
• 현재의 문자열 길이가 2 라면 👉 문자열 길이를 두 부분으로 나누어 홀수 개수를 세고 합친다.(합친건 다음 재귀 문자열이 된다.)
  • 그냥 s[0] 과 s[1] 로 나누면 된다.

    // 여기서 하나 배운게 있는데, char 문자 하나를 string 화 하려면 길이를 설정하는 생성자를 호출하여 1 로 설정해주면 된다.
    string s1(1, s[0]), s2(1, s[1]);
    

• 현재의 문자열 길이가 1 이라면 👉 재귀 종료 조건!, 현재 단계까지 구해왔던 홀수 개수의 최소값과 최대값 업데이트

---

조합에 대하여

• 나는 prev_permutation 을 사용하여 조합을 구했다.
  • (C++) 조합(Combination) 구현하기
• 근데 딱 2 개만 뽑는 조합을 구하는 것이기 때문에 굳이 나처럼 prev_permutation 쓸 필요 없이 이중 for문을 사용하여 조합을 구해도 된다.
  • 2 개 뽑는 조합은 아래와 같은 이중 for문으로 구할 수 있다. i와 j가 뽑은 두 개의 수가 된다.

    // 이런식!
    for(int i = 1; i <= N - 1; ++i)
        for(int j = i + 1; j <= N; ++j)
    

#include <bits/stdc++.h>

using namespace std;

int Min = INT_MAX;
int Max = 0;

int check_odd(string s) {
	int cnt = 0;
	for (int i = 0; i < s.length(); ++i) // 문자열의 한 문자 한 문자 다 검사 
		if ((s[i] - '0') % 2 == 1) // 해당 문자를 숫자로 변환했을 때 홀수라면
			++cnt;
	return cnt;
}

void odd_holic(string s, int totalCount) {
	if (s.length() == 1) {
		totalCount += check_odd(s);
		Min = min(Min, totalCount);
		Max = max(Max, totalCount);
		return;
	}
	else if (s.length() == 2) {
		string s1(1, s[0]), s2(1, s[1]);

		string next = to_string((s[0] - '0') + (s[1] - '0'));
		int nowCount = check_odd(s1) + check_odd(s2);
		odd_holic(next, totalCount + nowCount);
	}
	else if (s.length() >= 3) {
		vector<bool> comb(s.length() - 1, false);
		for (int i = 0; i < 2; ++i)
			comb[i] = true;

		do {
			vector<int> boundary;
			for (int i = 0; i < s.length() - 1; ++i) 
				if (comb[i])
					boundary.push_back(i);
			string s1 = s.substr(0, boundary[0] + 1);
			string s2 = s.substr(boundary[0] + 1, boundary[1] - boundary[0]);
			string s3 = s.substr(boundary[1] + 1, s.length() - 1 - boundary[1]);

			string next = to_string(stoi(s1) + stoi(s2) + stoi(s3));
			int nowCount = check_odd(s1) + check_odd(s2) + check_odd(s3);
			odd_holic(next, totalCount + nowCount);

		} while (prev_permutation(comb.begin(), comb.end()));
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	string N;
	cin >> N;
	
	odd_holic(N, 0);
	cout << Min << ' ' << Max;
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기