[알고리즘/브루트 포스] 2231번 : 분해합 - python

링크 : https://www.acmicpc.net/problem/2231

2231번: 분해합

 

---

• 문제
• 소요시간: 20분 이상

---

• 설계하기(접근방법) 

1. 입력받기

2. 알고리즘 해석

 

1) 1부터 n까지 분해합을 완전탐색을 통해 구해나간다

while문을 통해 각 자리수를 더한다

 

2) 분해합이 구해지면 for문을 break(그 것이 최소의 분해합이다)한다

 

3. 출력하기

 

 

---

• 코드(출력)

n = int(input())
cnt = 0
flag = 0
k = n

for i in range(1, n + 1):
    temp = 0
    check = i
    if i < 10:
        pass
    else:
        temp = i
    while (i):
        temp += (i % 10)
        i //= 10
    if temp == n:
        flag = 1
        answer = check
        break

if flag == 1:
    print(answer)
else:
    print(0)

---

• 얻어갈 부분

1. 분해합을 구하는 범위를 따로 구하려고 해서 시간이 오래걸렸다. 빅오를 초과히지 않는 범위라면은 그냥 문제를 풀자