알고리즘 문제/백준(BOJ)
BOJ 20164번 : 홀수 홀릭 호석 - python
요네리
2021. 5. 17. 22:58
Q. 문제
https://www.acmicpc.net/problem/20164
20164번: 홀수 홀릭 호석
호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게
www.acmicpc.net
A. 풀이
N = input()
def dfs(num, n, ok):
if len(num) == 1:
if int(num[0]) % 2 != 0:
n += 1
return n
elif len(num) == 2:
if int(num[0]) % 2 != 0:
n += 1
if int(num[1]) % 2 != 0:
n += 1
return dfs(str(int(num[0]) + int(num[1])), n, ok)
else:
for i in range(len(num)):
if int(num[i]) % 2 != 0:
n += 1
result = 0
if ok:
result = 0
else:
result = 100000000
for i in range(1, len(num) - 1):
for j in range(i + 1, len(num)):
a = int(num[:i])
b = int(num[i:j])
c = int(num[j:])
if ok:
result = max(result, dfs(str(a + b + c), n, ok))
else:
result = min(result, dfs(str(a + b + c), n, ok))
return result
print("{} {}".format(dfs(N, 0, False), dfs(N, 0, True)))
dfs 방식으로 문자를 계속 쪼개서 나오는 홀수의 갯수를 더했다.
최대 최소를 위해 더하는 조건을 결정해난 ok 파라미터를 추가하여,
한 함수로 재사용하여 최대값과 최소값을 구할 수 있게 만듬