[python_파이썬]백준_2231번_분해합_풀이

공부하는허딩크 : https://www.youtube.com/live/XxNgKJkVQ-E?feature=shared

분해합? 생성자? 뭐지? 천천히 어디에 적으면서 읽어보자.

245의 분해합은 256이 된다.

즉 분해합은 256

     생성자는 245

분해합 = 생성자 + 생성자 각 자리수의 합

이게 본문에 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 는 문구의 뜻이다. (나는 한국사람이 아닌듯.)

 

자연수 N이 주어질때 N은 분해합이다.

N으로 가장작은 생성자를 구하는 코드를 작성하면 된다.

 

<첫번째 시도 : 말도 안됨_그냥 본능대로 코드를 작성>

import sys

input = sys.stdin.readline

import itertools

A = [i for i in range(1, 10)]

N = input().strip()

for i in itertools.product(A, repeat = len(N)):

    if sum(i) + i[0] + i[1] + i[2] == int(N):

        print(sum(i))

    else: print(0)

 

조건중에 1 <= N <= 1,000,000 해당 조건을 어떻게 풀어야 할지 모르는 와중에

-1씩 하면서 계속 더해보는건 어때? 라는 그림이 그려졌다.

216이 주어진다면 215 + 2 + 1 + 5 이걸 기준으로 216과 계속 비교한다면?? => 바로 코드로 작성해보자.

 

<두번째 시도 : 이것도 말이 안됨 : 하지만 어느정도 방향은 비슷하게 가고 있음>

import sys

input = sys.stdin.readline

import itertools

N = int(input())

A = N

answer = []

while True:

    N -= 1

    for i in itertools.product(list(str(N)), repeat = len(str(N))):

        if sum(map(int, i)) + N == A:

            print(list(map(int, i)), N)

            answer.append(N)

    if N == 0:

        break

print(answer)

 

<세번째 시도 : 런타임에러_ 파이썬에서는 실행되던데.....>

import sys

input = sys.stdin.readline

N = int(input())

A = N

answer = []

while N > 0:

    N -=1  

    if sum(int(i) for i in list(str(N))) + N == A:

        answer.append(N)

if not answer:

    answer = 0

   

print(min(answer))

 

흠...while을 쓰면 안되는건가.....sum(int(i) for i in list(str(N))) 이거 만들어 내는데 int + str 조합이 안되서 개고생했건만...

아... 네번째 시도가 통과되고 나서 세번째 시도가 왜 안되는지 알겠다.

answer = 0이 되었을때 print(min(answer))를 주면 여기서 에러가 난다. OK

 

<네번째 시도 : 통과_이게 된다고??>

import sys

input = sys.stdin.readline

N = int(input())

A = N

answer = 0

while N > 0:

    N -=1  

    if sum(int(i) for i in list(str(N))) + N == A:

        if answer == 0:

            answer += N

        elif answer > N:

            answer = N

   

print(answer)

 

<다른사람 풀이 _ 내 코드와 비교 _ 이게 더 효율적이라고 함.>

나는 주어진 숫자에서 -1을 하면서 정리를 했다면,

아래의 코드는 0부터 주어진 숫자 -1 까지 하면서 첫번째 만족하는 i가 나오면 바로 return 아니면 0이 나오게 return

sum_of_numbers(i) 함수를 만든 후 

i = 198일 경우

첫번째 sum에 198 % 10인 8을 더해주고 i = i //10 = 19임

두번째 sum에 19 % 10인 9를 더해주고 i = i//10 = 1임

세번째 sum에 1 % 10인 1을 더해주고 i = i //10 = 0이니까 while문 탈출

즉 1 + 9 + 8을 더한 값이 sum_of_numbers함수에서 return되고 

if n = i + sum_of_numbers(i)를 만족하는 가장 작은 수가 먼저 나와서 답이 됨. => 이것도 괜찮네.

<★중요> 어떤 정수가 주어졌을때 %10을 하면 마지막자리수가 나온다

<★중요> 어떤 정수가 주어졌을때 //10을 해서 위에 넘겨주면 각 자리수를 구할 수 있다.

import sys

input = sys.stdin.readline

def sum_of_numbers(i): # 각 자릿수의 핪

    sum = 0

    while i > 0:

        sum += i%10

        i = i//10

    return sum

def get_m(n):

    for i in range(n):

        if n == i + sum_of_numbers(i):

            return i

    return 0

n = int(input())

print(get_m(n))

 

<다른사람 풀이 _ 나랑 생각이 반대네_이게 가장 효율적임>

import sys

input = sys.stdin.readline

N = int(input())

for i in range(1, N + 1):

    result = sum(map(int, str(i)))

    if N == i + result:

        print(i)

        break

    if i == N: #생성자 i와 입력값이 같다는 것은 생성자가 없다는 의미

        print(0)

       

 

<Chat GPT>

■ 브루트포스(Brute Force) 알고리즘 : 컴퓨터 과학에서 문제를 해결하기 위해 가능한 모든 경우의 수를 직접적으로 시도하여 해답을 찾는 방법을 말합니다. 이 방법은 단순하고 직관적이지만, 경우의 수가 많은 문제에 대해서는 실행 시간이 길어지는 단점이 있습니다. 주어진 문제의 특성에 따라 다른 알고리즘에 비해 효율이 낮을 수 있습니다.

부르트 포스 알고리즘의 단계는 다음과 같습니다:

1. 가능한 모든 경우의 수를 생성합니다.
2. 각 경우에 대해 문제의 조건을 만족하는지 검사합니다.
3. 조건을 만족하는 경우, 결과를 저장하거나 출력합니다.

 

부르트 포스 알고리즘은 모든 경우를 직접 탐색하기 때문에, 해를 구하는 데 필요한 시간 복잡도는 경우의 수에 따라 결정됩니다. 따라서 경우의 수가 많을수록 알고리즘의 실행 시간이 길어질 수 있습니다. 이러한 알고리즘은 경우의 수가 상대적으로 적고, 문제 해결에 다른 알고리즘이 적용하기 어려운 경우에 유용하게 사용됩니다.