2 분 소요

분해합

solved_ac[Class2] 분해합

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

216

예제 출력 1

198

문제 해석

브루트 포스 문제로 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 생성자를 찾기 위해서 for문을 1부터 입력 받은 수 만큼 돌리는데 가장 작은 생성자를 구해내야 하기 때문에 찾게 되면 break를 걸어서 빠져나온다.

브루트 포스(brute force)

brute: 무식한

force: 힘

무식한 힘으로 해석할 수 있다.

완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

  • 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.

  • 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.

  • 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.

    *너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊으므로 그때 따로 작성하도록 하겠다.

풀이

  • 자연수 입력 받음

  • 1인 경우 생성자가 없기 때문에 예외처리

  • 2부터 입력받은 수 n까지 for 문을 돌린다

  • 그 안에 반복문을 하나 더 만들어서 for 문의 index인 i 를 j에 넣어준 후 2중 반복문이 돌 때마다 j의 나머지 값을 sum에 더해준 후 j를 10으로 나눈 몫으로 업데이트 시켜준다 (각 자리수를 더해주기 위한 작업)

  • 10으로 계속 나눠서 몫이 0이 되면 2중 반복문을 빠져나온다

  • 각 자리수를 더한 후 자기 자신도 더해야 되기 때문에 for문의 index인 i를 더해준다.

  • 입력 받은 수 n과 같으면 index인 i값을 출력해주고 빠져나온다.

  • i가 입력 받은 수 - 1 까지 검사를 했는데도 생성자를 찾지 못한다면 생성자가 없는 것이기 때문에 0을 출력해준다

  • 정답을 찾은 것도 아니고 for문을 다 돈 것도 아니면 sum 을 0으로 업데이트 시켜주고 다시 돌려준다.

import sys

n = int(sys.stdin.readline())
sum = 0
j = 0
if n == 1:
    print("0")
else:
    for i in range(2, n):
        j = i
        while True:  
            sum += j % 10
            j = j // 10
            if j == 0:
                break
        sum += i   
        if sum == n:
            print(i)
            break
        elif i == n - 1:
            print("0")
        else:
            sum = 0

다짐

학기가 끝난지 약 1주일이 지났다. 많이 놀았고 많이 나태해졌기 때문에 9월까지 내가 목표한 바를 이루기 위해서는 지금부터 달려야한다.

class 2는 20문제가 남았기 때문에 하루에 5문제씩 4일 동안 끝낼것이다.

현재 시각 오후 2시 20분

복싱 가서 운동을 하고 알바를 가서 11시에 마치고 나서 연구실에 바로 온다.

목표한 5문제를 풀고 새벽 3시쯤에 퇴근

취침 후 아침 9시 전까지 연구실 출근

복싱 코치님과 일요일에 술 약속이 있으니깐 가기 전 까지 5문제를 다 풀고 블로그 포스팅까지 완료 후 간다.

월요일 부터는 친구들과 백준 스터디가 다시 시작하니 월요일에 class 2 5문제와 class 3 1문제를 푼다

화요일도 월요일과 마찬가지

수요일부터는 class 3 친구들이 이미 푼 문제를 나혼자 추가해서 다시 푼다 여기서 부터는 하루에 나혼자 푸는 문제 3문제 + 스터디 1문제

미해결 문제는 37문제니깐 1주일에 나 혼자 푸는 문제 15문제 + 스터디 5문제

최소 2주안에 끝낸다.

이 목표대로 간다면 7월 10일까지 class 3 완료가 된다.

그때와서 이 게시글을 다시 보겠다.

댓글남기기

참고