[백준] 수학3

백준 5086 배수와 약수

문제

https://www.acmicpc.net/problem/5086

풀이

def function():
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        pass
    elif m % n == 0:
        print("factor")
        function()
    elif n % m == 0:
        print("multiple")
        function()
    else:
        print("neither")
        function()


function()

if 문을 이용해서 input에 0이 나오면 끝내게 하고,
서로 나눠지면 답이 나오게 출력

---

백준 1037 약수

문제

https://www.acmicpc.net/problem/1037

풀이

N = int(input())
M = list(map(int, input().split()))

max_number = max(M)
min_number = min(M)

print(max_number * min_number)

약수가 주어졌을때 어떻게 하면 구할 수 있을까...
종이에다 적으면서 알아봣다.

그러다 보니까 규칙이 보여서 코드를 짯다

---

백준 11653 소인수 분해

문제

https://www.acmicpc.net/problem/11653

풀이

N = int(input())

while N != 1:
    for i in range(2, N + 1):
        if (N % i) == 0:
            print(i)
            N = N // i
            break

좀 무식한 방법인데 소수일지도 모르니까 2부터 시작해서 모든수를 다
다누어 주는것이다.
채점시간이 어마어마하게 길어서
다른 풀이를 찾아봤는데 , 시간이 굉장히 짧게 걸린 코드가 몇몇 있어서 가지고 왔는데

import sys

N = int(sys.stdin.readline())
ROOT = int(N ** 0.5)
i=2

while N:
    if i>ROOT: break

    if N%i == 0:
        print(i)
        N = N//i
    else:
        i+=1

if N > 1: print(N)

이 풀이는 저번에 알고리즘 풀었을때 심지어 내가 찾아봣던 방법이랑 비슷했다.

제곱근을 이용해서 구하게되면 시간 단축이 되는데
이 문제를 풀면서 생각도 못했다.

---

아... 멘붕

제목만 보고 들어갔을 때는
어! 초등학교때 배운거네... 이건 좀 할만하겠다!!
했는데... 심지어 정답률도 높앗다

누가 봐도 쉬울 것 같은 문제인데 나는

약수를... 어떻게 구하지?
소인수분해... 무엇?

최대공약수, 최소공배수는 사실상 반포기 상태다
이게 손으로 쓰면 아아 그치 이거지 하는데
막상 코드로 짤려니까, 이게아닌가? 그럼 이건...?
하는 경우가 너무 많다.

알고리즘 멘붕, 쉬운문제부터 다시 풀어봐야겟다...

알고리즘... 자존감 == 0