반응형

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

 

20164번: 홀수 홀릭 호석

호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게

www.acmicpc.net

 

주어진 수의 길이에 따라 연산을 수행해줍니다.

연산을 수행할 때마다 홀수의 개수를 더해주고, 수가 한 자리가 되었을 때 최종값을 업데이트해주었습니다.

 

#include <iostream>
#include <algorithm>
#include <string>
#define INF 2147483647
using namespace std;

string start;
int m1 = INF, m2 = 0;

int getOddCount(string& s) {
	int cnt = 0;
	for (int i = 0; i < s.size(); i++)
		if (s[i] % 2) cnt++;
	return cnt;
}

void oddHolic(string s, int c) {
	int oddCnt = getOddCount(s);
	if (s.size() == 1) {
		m1 = min(m1, c + oddCnt);
		m2 = max(m2, c + oddCnt);
	}
	else if (s.size() == 2) {
		oddHolic(to_string((s[0] - '0') + (s[1] - '0')), c + oddCnt);
	}
	else {
		for (int i = 1; i < s.size() - 1; i++) {
			for (int j = i + 1; j < s.size(); j++) {
				oddHolic(to_string(stoi(s.substr(0, i)) + stoi(s.substr(i, j - i)) + stoi(s.substr(j))), c + oddCnt);
			}
		}
	}
}

int main() {
	cin >> start;
	oddHolic(start, 0);
	cout << m1 << " " << m2;
}
반응형

'Algorithm' 카테고리의 다른 글

백준 2922 : 즐거운 단어  (0) 2021.11.17
백준 1600 : 말이 되고픈 원숭이  (0) 2021.11.16
백준 2045 : 마방진  (0) 2021.11.16
백준 8980 : 택배  (0) 2021.11.16
백준 18808 : 스티커 붙이기  (0) 2021.11.16

+ Recent posts