[DFS/BFS/완전탐색] 2231번 - 분해합(완전탐색)

[백준] 2231번 - 분해합

풀이 시간: 20분 이내

 

1) 문제 해결 아이디어

자연수 N의 가장 작은 생성자를 구하는 문제로 완전탐색으로 풀어야 하는 문제다.

N = M + M의 각 자리수의 합 → N의 생성자 = M

우리가 구해야할 값은 M이고 여기서 1 <= N <= 1,000,000 이라고 했으므로 M은 1부터 n까지 사이의 모든 경우의 수를 검사해본다. 제일 처음 위 조건을 만족하는 수가 가장 작은 생성자가 된다.

 

<문자가 원소인 리스트 int형 리스트로 형 변환>

1. map 함수 이용

list1 = ['2', '3', '4']	
likst2 = list(map(int, list1))	# 문자로 된 리스트 int형 리스트로 형변환
print(list2)	# [2, 3, 4]

2. List Comprehension

list1 = ['2', '3', '4']	
likst2 = [int(x) for x in list1]	# 문자로 된 리스트 int형 리스트로 형변환
print(list2)	# [2, 3, 4]

 

[참고] https://coding-groot.tistory.com/22https://coding-groot.tistory.com/22

[파이썬] 리스트 변형 :: 리스트를 원하는 형태로 바꾸기, 리스트 형변환

 

2) 소스코드

n = int(input())  # 분해합(자연수)
res = 0  # 생성자

# 생성자(M)의 값 찾기
for i in range(1, n + 1):
  # i + i의 각 자리수의 합
  cnt = i + sum(map(int, str(i)))
  if(cnt == n):
    res = i
    break

print(res)