완전탐색(브루트포스) 문제 및 풀이 (Python)

코테 준비를 위한 알고리즘 공부 순서 

 위 링크에서 완전탐색(브루트포스) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다. 

 

 

4. 완전탐색(브루트포스)

• 브루트(Brute): 무식한 + 포스(Force): 힘
• 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻.
• 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.
• 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.

참고링크

 

문제

(❌ 표시는 혼자 못푼 문제)

 

2023. 12. 06. 2일차(4)

1. 2231번 분해합 (브론즈2)  문제링크

문제 해석

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합 = N+N각 자리수의 합

자연수 M의 분해합이 N일 경우, M을 N의 생성자라 한다.

ex) 256(=245+2+4+5) -> 따라서 245는 256의 생성자가 된다.

어떤 자연수의 경우에는 생성자가 없을 수도 있고, 여러개 있을 수도 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구하여라.

제한: 2초 192MB

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

아이디어

1부터 N까지 올라가면서 분해합을 구하고 주어진 N과 동일한 값이 나오면 멈춘다.

최대 1,000,000 번 돌기 때문에 O(n) 이다.

 

코드

import sys

def _input():
    return sys.stdin.readline().strip()


def fun(N):
    for i in range(1, N + 1):
        res = i
        temp = i

        while temp != 0:
            res += temp % 10
            temp = temp // 10

        if N == res:
            return i

    return 0


N = int(_input())

print(fun(N))

 

추가 문제

2. 2309번 일곱 난쟁이 (브론즈1)  문제링크

 

3. 10448번 유레카 이론 (브론즈1)  문제링크

 

4. 1436번 영화감독 숌 (실버5)  문제링크

 

5. 1018번 체스판 다시 칠하기 (실버4)  문제링크

 

6. 17384번 진우의 달 여행(Small) (실버4)  문제링크

 

7. 3085번 사탕 게임 (실버3)  문제링크

 

8. 2503번 숫자 야구 (실버3)  문제링크

 

9. 1912번 연속합 (실버2)  문제링크

 

10. 1182번 부분수열의 합 (실버2)  문제링크

 

11. 2529번 부등호 (실버2)  문제링크

 

12. 14620번 꽃길 (실버2)  문제링크

 

13. 14889번 스타트와 링크 (실버2)  문제링크

 

14. 1992번 쿼드트리 (실버1)  문제링크

 

15. 1189번 컴백홈 (실버1)  문제링크

 

16. 14888번 연산자 끼워넣기 (실버1)  문제링크

 

17. 12919번 A와 B 2 (골드5)  문제링크

 

18. 1027번 고층 건물 (골드4)  문제링크

 

19. 16637번 괄호 추가하기 (골드4)  문제링크

 

20. 17406번 배열 돌리기 4 (골드4)  문제링크

 

21. 14658번 하늘에서 별똥별이 빗발친다 (골드3)  문제링크

 

22. 17136번 색종이 붙이기 (골드2)  문제링크