우주의 IT 소행성

이전 포스팅 한 소수 구하기를 응용하여 풀 수 있다.

주어진 수를 소수의 작은 순서로 나누어 떨어지는 데 까지 나누고

마지막 남은 나머지가 소수 리스트 안에 있다면 해결

소수 리스트 안에 없다면 소인수 분해가 불가능 하다고 판단.

import math
n = int(input())
array = [True for i in range(n + 1)]

for i in range(2, int(math.sqrt(n)) + 1):
    if array[i]:
        j = 2
        while i * j <= n:
            array[i * j] = False
            j += 1


data = []
for i in range(2, n + 1):
    if array[i]:
        data.append(i)

while True:
    if n in data:
        print(n)
        break

    elif n == 1:
        break

    for i in range(2, n + 1):
        if n % i == 0:
            n //= i
            print(int(i))
            break

주어진 범위 내에서 소수를 찾아, 그 소수들의 합과 최소값을 가지는 소수를 출력하는 문제이다.

에라토스테네스의 체 알고리즘을 이용하여 소수를 구해주면 된다.

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

1) 2부터 N까지 모든 자연수를 나열

2) 남은 수 중 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3) 남은 수 중에서 i의 배수를 모두 제거한다.

4) 더이상 반복할 수 없을 때 까지 2, 3을 반복

시간 복잡도는 O(NloglogN)으로 선형 시간에 필적할 수준.

하지만 메모리를 많이 잡아먹는 단점이 있으니 잘 확인해보아야 한다.

수열을 묶어 최대의 값을 가져오는 문제 (그리드)

어떤 경우에 최대 값이 나올 수 있는가에 대해 생각 해보자.

입력 된 값들을 오름차순으로 정렬했을 때

앞부분에 [음수, 0, 1]에 해당하는 값이 나온다면 이 값을 우선 계산해주어야 한다.

0번째와 1번째의 값 비교

음수, 음수 -> 곱한다

음수, 0 -> 곱한다

음수, 양수 -> 더한다

이렇게 앞부분의 양수가 아닌 값( 1 제외 )을 없애준 후

나머지는 뒤에서부터(큰 순서로) 2개씩 묶어 곱해주면 된다.

ex) -1 2 1 3일 경우

정렬하면 -1 1 2 3

-1과 2는 (음수, 양수)이기에 더해준다. -> 0

뒤에 2, 3을 묶어 곱해준다 -> 6

0 + 6 -> 6

n = int(input())
data = list(int(input()) for _ in range(n))
data.sort()

result = 0
while True:
    if len(data) == 0:
        break
    elif len(data) == 1:
        result += data.pop(0)
        break
    elif data[0] == 0 and len(data) >= 2:
        result += data.pop(0) + data.pop(0)
    elif data[0] < 0 and len(data) >= 2:
        tmp1 = data.pop(0)
        tmp2 = data.pop(0)
        if tmp2 < 0:
            result += tmp1 * tmp2
        elif tmp2 > 0 and (len(data) + 2) % 2 == 0:
            result += tmp1 + tmp2
        elif tmp2 > 0 and (len(data) + 2) % 2 == 1:
            data.insert(0, tmp2)
            data.insert(0, tmp1)
            tmp1 = data.pop()
            tmp2 = data.pop()
            result += tmp1 * tmp2

    elif len(data) >= 2:
        tmp1 = data.pop()
        tmp2 = data.pop()
        if tmp1 == tmp2 == 1:
            result += tmp1 + tmp2
        elif tmp1 == 1 or tmp2 == 1:
            result += tmp1 + tmp2
        else:
            result += tmp1 * tmp2
print(result)

입력값이 0 또는 1밖에 없으니 0이나 1중 하나를 선택하여 split 해준다.

1을 split 했다고 가정했을 때

0011100010 -> '00', '', '000', '', '0'

이 되는데 이때 전체 숫자 수 에서 ''의 수를 카운트해서 빼주면 된다.

이때 0011100010보다 1100011101이 더 작을수가 있기에

그 경우의 수를 생각하여준다.

s = input()
s2 = ''

for i in s:
    if i == '0':
      s2 += '1'
    else:
        s2 += '0'

a = s.split('1')
b = s2.split('1')
result = min((len(a) - a.count('')), (len(b) - b.count('')))
print(result)