완전탐색 문제
- 완전탐색은 말 그대로 모든 답안을 확인해 보고 답을 배출하는 방식으로
답이 늘어나면 시간복잡도도 같이 늘어나 O(n)이다.
아래의 문제를 푸는데 시간이 많이 걸렸다.
너무 어떤 식으로 문제를 풀어나가고 자료형의 이해를 도가 부족해 문제를 풀지 못했다.
그래서 팀원에게 도움을 받았다.
분해합 baekjoon 2231 python
문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다.
어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다.
따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다.
반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
N이라는 숫자가 주어지면 이 숫자를 만들기 위한 M(생성자)과 M의 자릿수의 합을 구하는 문제이다.
처음에는 문제를 이해하는데도 시간이 너무 많이 걸렸고
N이 256이라면 map 함수의 이해도 부족으로 시간이 많이 발생했다.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.
예제 입력 1
216
예제 출력 1
198
그리도 출력에서 M(생성자)가 없는 경우와 생성자가 여러 개일 경우를 생각해 문제가 발생했다.
이 문제를 해결하기 위해서 최소값을 구하는 min을 이용해 해결했다.
n = int(input())
answer = []
for i in range(1, n+1):
num = list(map(int,str(i)))
if n == sum(num) + i:
answer.append(i)
if answer:
print(min(answer))
else:
print(0)
해설
1. input값을 integer정수 형로 받아준다.
2. for 반복문을 1 부터 입력받은 n까지 돌기 위해 n+1번까지 돈다.
3. map 함수를 이용해 i를 하나하나 리스트로 만든다 (string으로 변경을 해서 리스트로 만들어 줘야 한다.)
4. if문을 이용해 M의 자리수합 리스트와 M의 더한 값이 N과 같은지 비교한다.
5. 같은 값들을 answer에 저장한다.
6. 조건문을 통해 answer의 최솟값 min을 출력하거나 없다면 0을 출력한다.
마무리
자료형의 특징 이해와 문제를 많이 접해 보지 않아 어떤 식으로 접해야 할지 감도 안 잡혔다.
다양한 문제를 풀어보고 최소 3가지의 풀이를 정리해야겠다.