BAEKJOON : 1212, 2089, 17103

No. 1212

1. Problem

2. My Solution

• 첫 번째 방법 (직접 구현)

import sys

def oct_to_bin(oct_num):

    result = ''

    for i in oct_num:

        temp = ''

        while True:
            a,b = divmod(i,2)
            if a == 0:
                temp += str(b)
                temp += str(a)
                break
            else:
                temp += str(b)
                i = a

        if len(temp) == 2:
            temp += '0'
        elif len(temp) == 4:
            temp = temp.rstrip('0')

        result += temp[::-1]
   
    while result[0]=='0':
        result = result.lstrip('0')

    return result

oct_num = list(map(int,list(str(sys.stdin.readline().rstrip()))))

if oct_num[0] == 0:
    print(0)
else:
    print(oct_to_bin(oct_num))

• bin() 함수 이용

oct_num = int(sys.stdin.readline().rstrip(), 8)
print(bin(oct_num)[2:])

No. 2089

1. Problem

2. Others' Solutions

• 10진수를 2진수로 변환하는 원리를 그대로 이용
• 2로 계속 나누지 않고 -2로 나눔

import sys

n = int(sys.stdin.readline().rstrip())

if n == 0:
    print(0)
    exit()

result =''

while(True):
    a,b = divmod(n,-2)
    
    if n == 0:
        break
    elif n % -2:
        result += '1'
        n = n//-2 +1
    else:
        result += '0'
        n //= -2

print(result[::-1])

3. Learned

• 10진수를 2진수로 변환하는 원리를 그대로 이용하자

-13 = -2*(7) + 1
 7  = -2*(-3) + 1
-3  = -2*(2) + 1
 2  = -2*(-1) + 0
-1  = -2*(1) + 1
 1  = -2*(0) + 1

• 하지만 파이썬에서 음수로 나머지 연산을 수행하면 나머지가 무조건 양수가 나오지 않음 (C언어는 양수)

No. 17103

1. Problem

2. My Solution

• 에라토스테네스의 체 이용
• 같은 쌍 제거를 위해 n//2 까지만 판단

import sys
import math

test_n = int(sys.stdin.readline().rstrip())

prime = [False,False] + [True] * 999999

for i in range(2,int(math.sqrt(1000000))+2,1):
    if prime[i] == False:
        continue
    else:
        for j in range(i+i, 1000001, i):
            prime[j] = False

for _ in range(test_n):

    n = int(sys.stdin.readline().rstrip())

    gold_num = []

    for i in range(2, (n//2)+1, 1):
        if prime[i] == True and prime[n-i] == True:
            gold_num.append([i,n-i])
    
    print(len(gold_num))

3. Others' Solutions

• prime 리스트에 소수만 append -> 시간 단축 3420ms -> 1264ms

import sys
input = sys.stdin.readline

nums = [1] * 1000001
prime = []
for i in range(2, 1000001):
    if nums[i] == 0:
        continue
    prime.append(i)
    for j in range(2*i, 1000001, i):
        nums[j] = 0

for _ in range(int(input())):
    n = int(input())
    count = 0
    for i in prime:
        if i > n//2:
            break
        if nums[i] and nums[n-i]:
            count += 1
    print(count)

4. Learned

• 순서만 다르고 요소의 구성이 같은 쌍을 제거하기 위해 n//2 까지만 비교
• 시간을 최소로하는 방법도 추가적으로 생각해보자

n = 10 일 때
1 2 3 4 5 6 7 8 9 10  5를 기준으로 양쪽의 조합이 같음