BAEKJOON : 9613, 17087, 1373

No. 9613

1. Problem

2. My Solution

• 가능한 모든 쌍을 구하기 위해 itertools.combinations() 함수 이용
• 또는 2중첩 for 문을 이용하여 모든 쌍 구할수도 있음 (2798번 문제 참고)
• GCD 유클리드 호제법 (알고리즘) 이용

import sys
import itertools

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b) 

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

for _ in range(test_n):
    test_case = list(map(int,sys.stdin.readline().rstrip().split()))
    pair = list(itertools.combinations(test_case[1:],2))

    sum = 0

    for i in pair:
        result = gcd(max(i), min(i))
        sum += result
    
    print(sum)

3. Learned

• 요소의 가능한 모든 조합을 구하기 위해서는 파이썬의 itertools.combinations() 함수를 이용하자
• 유클리드 알고리즘 (호제법)
  - 2개의 자연수의 최대공약수를 구하는 알고리즘
  - 비교대상의 두 개의 자연수 a와 b에서 (a>b) a를 b로 나눈 나머지를 r 이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다." 라는 원리를 활용한 알고리즘

---

No. 17087

1. Problem

2. My Solution

• 첫 번째 방법
• 정확하게 동생(들)의 위치에 도달하기 위해선 동생(들)의 위치 간격이 배수 관계여야함
• 가장 가까운 동생의 위치에 도달하기 위한 d 값을 구하고 d 값으로 남은 동생들의 거리를 나머지 연산
• 결과 -> "틀렸습니다"

import sys

n,s = map(int,sys.stdin.readline().rstrip().split())
loc_list = list(map(int,sys.stdin.readline().rstrip().split()))

d_list = []

for i in range(len(loc_list)):
    d = abs(loc_list[i] - s)
    d_list.append(d)

result = min_d = min(d_list)

for i in range(len(loc_list)):
    if abs(loc_list[i] - s) % min_d != 0:
        result = 1

print(result)


// 반례
3 2
6 12 24
1 (2가 나와야 정답)

• 두 번째 방법 (유클리드 호제법 이용)
• 모든 인접한 두 요소의 최대 공약수를 구함 (시간복잡도 < 100000)
• 단, 최대 공약수 중에 가장 작은 값, 수빈이의 위치에서 가장 가까운 동생의 거리까지도 비교 대상이 됨

import sys

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

n,s = map(int,sys.stdin.readline().rstrip().split())
loc_list = list(map(int,sys.stdin.readline().rstrip().split()))

d_list = []

for i in range(len(loc_list)):
    d = abs(loc_list[i] - s)
    d_list.append(d)

result = min_d = min(d_list)

for i in range(len(loc_list)-1):
    temp= gcd(abs(loc_list[i]-s), abs(loc_list[i+1]-s))

    if result > temp:
        result = temp

print(result)

3. Learned

• "최댓값" 이라는 단어에서 최대공약수라는 문제 해결 핵심 원리를 파악할 줄 알아야함

---

No. 1373

1. Problem

2. My Solution

• 2진수의 길이가 3의 배수가 되도록 변환 (맨 앞에 0을 추가)
• 3자리 마다 4,2,1 을 곱한 뒤 누적합을 얻어냄

import sys

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

if len(binum) % 3 == 1:
    binum.insert(0,0)
    binum.insert(0,0)
elif len(binum) % 3 == 2:
    binum.insert(0,0)

weight = 4
sum = 0
result =''

for i in range(len(binum)):
   
    sum += binum[i] * weight
    weight = weight // 2

    if weight == 0:
        weight = 4
        result += str(sum)
        sum = 0
    
print(result)

3. Others' Solutions

• oct() 함수 이용

print(oct(int(input(),2))[2:])

4. Learned

• 2진수에서 8진수로의 변환은 2진수를 3개씩 나눠서 각 자리마다 십진수로 표현하는 것
• int("숫자", 2) -> 2진수로 입력