[C++][백준] 홀수 홀릭 호석(20164) - DFS

문제

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

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

• 수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.

• 수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.

• 수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.

• 수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.

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

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

 

입력

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

 

출력

DFS로 풀이하였습니다.

 

dfs 함수는 현재 가지고 있는 수, 현재 홀수 갯수를 매개변수로 받습니다.즉 예제에서 dfs(82019, 0)을 최초 호출하게 됩니다.

 

먼저 홀수 갯수를 계산합니다.

// 홀수 갯수 카운트
int oddCnt = cnt;

while (N) {
    if ((N % 10) % 2 != 0) {
      oddCnt++;
    }
    N = N / 10;
}

 

제가 구현한 dfs에서는 자리수에 따라 다른 로직을 수행하게 됩니다.자리수는 간단히 int를 string 타입으로 변환 후 size() 함수를 호출하여 구할 수 있습니다.

string strN = to_string(n);
int size = strN.size();

 

1. 한자리 자리수일 경우

더이상 아무것도 하지 않고 종료합니다. 홀수 수를 갱신합니다.

if (size == 1) {
    if (oddCnt < minValue) {
        minValue = oddCnt;
    }

    if (oddCnt > maxValue) {
        maxValue = oddCnt;
    }
 }

 

2. 두자리 자리수일 경우

수를 2개로 나눠서 합을 구하여 새로운 수로 생각합니다.

else if (size == 2) {
    int next = (n / 10) + (n % 10);
    dfs(next, oddCnt);
}

 

3. 세자리 이상인 경우

임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각합니다.

 

수 82019를 3개의 수로 분할하는 모든 경우를 생각해보겠습니다. 

즉 3개의 수로 분할하는 모든 경우는 (N-1)C2 조합에서 1이 2개인 케이스를 기준으로 수를 자르면 됩니다.

 

 

 

i를 3에서 15까지 증가시키면서 1이 두번 들어가는지 검사하고

두번 들어간다면 해당 케이스를 기준으로 수를 자르면 됩니다.

 

해당 코드는 아래와 같습니다.

for (int i = 3; i < pow(2, size - 1); i++) {
    if (canDivide(i, size - 1)) {
        vector<int> DivideIdx = getDivideIdx(i, size - 1);

        string first = strN.substr(0, DivideIdx[1] + 1);
        string second = strN.substr(DivideIdx[1] + 1, DivideIdx[0] - DivideIdx[1]);
        string third = strN.substr(DivideIdx[0] + 1);

        int firstN = stoi(first);
        int secondN = stoi(second);
        int thirdN = stoi(third);

        dfs(firstN + secondN + thirdN, oddCnt);
    }
}

i는 3에서 15까지 증가합니다.

canDivide 함수는 i에 1이 두번 들어가는지 검사합니다. 

두번 들어가는 경우 세 덩어리로 나눌 인덱스를 구하고 3개를 더한 값을 새로운 수로 생각하여 dfs 합니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <string>
#include <cmath>
#include <vector>

using namespace std;

int N;

int maxValue = -1;
int minValue = 987654321;

// 1을 2개 포함하는지 확인하는 메서드
bool canDivide(int n, int size) {
	int cnt = 0;
	for (int i = 0; i < size; i++) {
		if (n & (1 << i)) {
			cnt++;
		}
	}

	if (cnt == 2) return true;
	else return false;
}

vector<int> getDivideIdx(int n, int size) {
	vector<int> result;

	for (int i = 0; i < size; i++) {
		if (n & (1 << i)) {
			result.push_back(size - 1 - i);
		}
	}
	return result;
}

void dfs(int n, int cnt) {
	// size 계산
	int N = n;
	string strN = to_string(n);
	int size = strN.size();
	
	// 홀수 갯수 카운트
	int oddCnt = cnt;
	
	while (N) {
		if ((N % 10) % 2 != 0) {
			oddCnt++;
		}
		N = N / 10;
	}

	if (size == 1) {
		if (oddCnt < minValue) {
			minValue = oddCnt;
		}

		if (oddCnt > maxValue) {
			maxValue = oddCnt;
		}
	}
	else if (size == 2) {
		int next = (n / 10) + (n % 10);
		dfs(next, oddCnt);
	}
	else {
		for (int i = 3; i < pow(2, size - 1); i++) {
			if (canDivide(i, size - 1)) {
				vector<int> DivideIdx = getDivideIdx(i, size - 1);
				
				string first = strN.substr(0, DivideIdx[1] + 1);
				string second = strN.substr(DivideIdx[1] + 1, DivideIdx[0] - DivideIdx[1]);
				string third = strN.substr(DivideIdx[0] + 1);

				int firstN = stoi(first);
				int secondN = stoi(second);
				int thirdN = stoi(third);

				dfs(firstN + secondN + thirdN, oddCnt);
			}
		}
	}
}

int main() {
	cin >> N;

	dfs(N, 0);

	cout << minValue << " " << maxValue;

	return 0;
}