백준 20164 홀수 홀릭 호석 C풀이 - DFS

홀수 중독자 호석이 이야기다.

주어진 10^9 이하의 숫자를 쪼개고 쪼개서 홀수를 가장 많이 보고 싶다고 한다.

 

문제의 조건은 다음과 같다.

1. 마지막 한 자리만 남기 전까지의 과정에서 가장 홀수를 많이 보는 경우와 적게 보는 경우를 구한다.

2. 시작 숫자부터 중간과정의 숫자에서 나타나는 모든 홀수를 세지만 마지막 한 자리만 남았을 때는 세지 않는다.

3. 두 자리 숫자는 두 개로 나누면 되지만, 수가 세 자리 이상일 경우 임의의 자리에서 '알아서' 잘라서 3종류의 숫자로 만들어서 다 더해서 다음 숫자를 구한다.

 

문제의 접근 방식 및 해결방식은 다음과 같다.

0. 완전탐색

1. 자릿수마다 처리하는 방식을 다르게 한다.

2. 세 자리가 넘어가는 수를 다룰 때는 자를 위치를 두 곳 정하고 다음 숫자를 구해 DFS로 잘라 들어간다.

3. 마지막 한 자리가 남을 때까지 반복해서 2를 수행한다.

 

고생한 점은 다음과 같다.

1. 오랜만에 문자열로 다루려니 힘들었다.

2. 백준의 gcc 컴파일러에선 itoa 함수를 사용할 수 없기 때문에 직접 구현하였는데, itoa 함수 내에서 지역변수로 char 배열을 만들어서 리턴하니 자꾸 문제가 발생해서, 함수를 호출하기 전에 선언하고 그 주소에 접근하여 값을 수정하는 식으로 구현하였다.

 

전체 코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int Max, Min = 987654321;

char Original[11];
// int -> char[]
void itoa(char  tmp[10], int a) {
	//0이 들어올 경우 '0'을 넣어주고 바로 종료
	if (a == 0) {
		tmp[0] = '0';
		return;
	}
	//int a의 자릿수(cnt) 구하기
	int t = a;
	int cnt = 1;
	while (t / 10) {
		t /= 10;
		cnt++;
	}
	//맨 윗자리부터 차례대로 배열에 넣어주기
	int num = 0;
	for (int i = 0; i < cnt; i++) {
		t = a;
		for (int j = cnt - 1 - i; j > 0; j--) {
			t /= 10;
		}
		tmp[num++] = t % 10 + '0';
	}
	return;
}
//현재 숫자 중 홀수의 개수 구하기
int odd(char * c) {
	int ret = 0;
	for (int i = 0; i < strlen(c); i++) {
		if ((c[i]-'0') % 2) {
			ret++;
		}
	}
	return ret;
}

//숫자 잘라서 들어가기 c=현재 숫자 oddnum 현재 홀수 개수
int dfs(char* c, int oddnum) {
	//숫자가 한자리일 경우 갱신 후 종료
	if (strlen(c) == 1) {
		if (oddnum < Min) Min = oddnum;
		if (oddnum > Max) Max = oddnum;
		return 0;
	}
	//두 자리일 경우 하나씩 잘라서 더해서 들어감
	if (strlen(c) == 2) {
		int tmp1 = c[0]-'0';
		int tmp2 = c[1] -'0';
		char tmp[10] = { 0 };
		itoa(tmp, tmp1 + tmp2);
		dfs(tmp, oddnum+odd(tmp) );
	}
	//세 자리일 경우 위치를 i, j로 정하고 잘라서 더한 후 탐색
	if (strlen(c) >= 3) {
		for (int i = 1; i < strlen(c); i++) {
			for (int j = i + 1; j < strlen(c); j++) {
				char tmp1[10] = { 0 }, tmp2[10] = { 0 }, tmp3[10] = { 0 };
				//0~i-1 까지 숫자 1
				strncpy(tmp1, c, i);
				//i ~ j-1 까지 숫자 2
				strncpy(tmp2, c + i, j - i);
				//j ~ 끝까지 숫자 3
				strncpy(tmp3, c + j, strlen(c) - j);
				//tmp = 숫자1 + 숫자2 + 숫자3
				char tmp[10] = { 0 };
				itoa(tmp, atoi(tmp1) + atoi(tmp2) + atoi(tmp3));
				//탐색
				dfs(tmp,oddnum+odd(tmp));
			}
		}

	}
	return 0;

}

int solve() {
	//첫 숫자 홀수 개수 구한 후 탐색
	dfs(Original, odd(Original));
	return 0;
}


int main() {
	scanf("%s", Original);
	solve();
	printf("%d %d\n", Min, Max);
	return 0;
}