★Math & Geometry Upper-Intermediate I - 6 Solved★

★ 1002 터렛 ★

 

for _ in range(int(input())):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    
    d = (x1-x2)**2 + (y1-y2)**2

    if d > (r1+r2)**2: print(0)
    elif d == (r1+r2)**2: print(1)
    elif (r1+r2)**2 > d > (r1-r2)**2: print(2)
    else:
        if r1!=r2:
            if d == (r1-r2)**2: print(1)
            else:print(0)
        else:print(-1)

 

🤽🏻‍♂️ 두 원의 위치 관계에 따른 두 원 교점의 개수

 

🤽🏻‍♂️ 두 원의 위치 관계는 크게 6가지로 나뉜다.

 

🤽🏻‍♂️ 두 원의 중심 사이의 거리를 기준으로 6가지를 자세하게 나눌 수 있다.

(두 원의 중심 사이의 거리를 d라고 하고, 두 원의 반지름을 각각 r1, r2라고 하면)

① d > (r1+r2) - 두 원이 아예 만나지 않음 - 교점 0개 

 

② d = (r1+r2) - 두 원이 서로 외접함 - 교점 1개

 

③ (r1+r2) > d > |r1-r2| - 두 원이 겹침 - 교점 2개

 

→ 아래 3가지 |r1-r2| >= d인 경우 중에서

④ r1 = r2 - 두 원이 아예 겹침 - 교점 무수히 많음

 

⑤ r1 ≠ r2이고 d = |r1-r2| - 한 원이 다른 원에 내접함 - 교점 1개

⑥ r1 ≠ r2이고 |r1-r2| > d - 한 원이 다른 원에 들어감 - 교점 0개

---

★ 13908 비밀번호 ★

 

from math import factorial

def combination(a,b): #aCb
    return factorial(a)//(factorial(b)*factorial(a-b))

n,m=map(int,input().split())
if m>0:input()
ans=10**n
for i in range(1,m+1):
    ans+=(((-1)**i)*(combination(m,i))*((10-i)**n))
print(ans)

 

🤽🏻‍♂️ BF로 풀 수 있으나, 포함과 배제의 원리로 접근해 풀어보자!

 

🤽🏻‍♂️ n개의 자리수에서 m개의 서로 다른 숫자가 포함된 비밀번호의 수인 정답을 A라고 하면, 포함과 배제의 원리에 의해

A = 10^n - mC1x(9^n) + mC2x(8^n) - mC3x(7^n) + ... 

 

① 전체 경우의수 10^n

② m개 숫자 종류 각각 1개씩만 비밀번호에 들어가지 않을 경우는 9^n이고, 이를 전체 경우의 수에서 빼야 함

(비밀번호에는 이를 포함해야 하므로) - mC1만큼 경우의 수 존재

③ 여기서, 공통적으로 빼진 부분이 있으므로 (예를 들면 4자리 수에서 각각 3과 4가 안들어간 경우를 뺐을 때, 예를 들어 1256은 두 번 빼짐),

포함과 배제의 원리에 의해 겹친 부분을 다시 더해줘야 함 - 이는 mC2개의 가짓수에서, 이제 두 개가 공통적으로 안들어간 경우 8^n을 곱한 경우의 수를 다시 더해줌

④ 이젠, 포함과 배제의 원리에 의해 세 개의 숫자가 다시 더해줬으므로, 빼줘야 함 - 이렇게 반복

 

mCn = (n!)/(r!(m-n)!)

 

🤽🏻‍♂️ 위 A를 다시 정리해보자면,

---

★ 2477 참외밭 ★

 

def get_area(pos,K,h,w,sh,sw,i):
    w = i[pos][1]
    h = i[pos-1][1]

    if pos==5: sh = h-i[0][1]
    else: sh = h-i[pos+1][1]
    
    if 4<=pos: sw = i[pos-4][1]
    else: sw = i[pos+2][1]

    return (K*(h*w-sh*sw))

K=int(input())
n=0
i=[]
ds=[]

for _ in range(6):
    d,l=map(int,input().split())
    i.append((d,l))
    ds.append(d)

ds.sort()

if ds==[1,1,2,3,3,4]: n=2
elif ds==[1,2,2,3,4,4]: n=1
elif ds==[1,2,2,3,3,4]: n=4
else: n=3

pos = [pair[0] for pair in i].index(n)


print(get_area(pos,K,0,0,0,0,i))

 

🤽🏻‍♂️ 총 4가지 모양의 참외밭이 주어져 있고, 동서남북 방향을 각각 1234로 했을 때, 각 참외밭의 긴 가로길이를 pos 변수에 넣고, 이를 기준으로 앞 뒤 방향에 따른 변 길이를 이용해 큰 직사각형 넓이 - 작은 직사각형 넓이를 구한다

 

🤽🏻‍♂️ 여러 if문으로 상황에 따라 생각해야 하는 기하학 문제

 

🤽🏻‍♂️ 큰 직사각형의 가로와 세로 길이를 각각 i와 j로 index()를 이용해 구하고, 이로부터 index 기준 3씩 떨어진 게 작은 직사각형의 가로와 세로임을 idea로 알아채면 아래와 같이 매우 간단하게 코딩 가능! (이 때 index + 3에 오류가 나지 않게끔 일부러 똑같은 숫자를 붙여 list를 2배로 해준다. - idea 기억하기)

n=int(input())
x=[int(input().split()[1])for _ in range(6)]*2
i=x.index(max(x))
j=x.index(max(x[i-1],x[i+1]))
print(n*(x[i]*x[j]-x[i+3]*x[j+3]))

---

★ 7908 Will It Stop? ★

import math
n = int(input())
if int(math.log(n,2)) == math.log(n,2):
    print('TAK')
else:
    print('NIE')

🤽🏻‍♂️ 소인수분해 결과 2로만 이루어진 수, 즉 2의 제곱수라면 결국 n이 1이 되므로 TAK 출력 / 그렇지 않고 2가 아닌 다른 소인수가 존재한다면 무조건 무한반복문에 걸려서 NIE 출력.

 

🤽🏻‍♂️ 모든 자연수는 2^k*p(p는 소수 또는 1)로 나타낼 수 있는데, p가 1인 경우 2의 제곱수이므로 이 때는 TAK 출력 / p가 1이 아닌 소수인 경우 언젠가는 p 홀수로 인해 n이 3*n+3으로 연산되는 부분에 걸리게 되고, 즉 3이 곱해지므로 3이 지워지지 않게 되기에(3의 배수 유지) 무한반복문에 갇혀서 NIE 출력

---

★ 13662 Elevador ★

🤽🏻‍♂️ 주어진 직사각형에서 두 원을 넣을 수 있는 지 판별하는 기하학 문제

: 위 두 원의 반지름을 r1, r2라 하고 직사각형의 가로 길이를 W, 세로 길이를 H라 하자(왼쪽 원 A, 오른쪽 원 B). A를 직사각형의 왼쪽 위에 최대한 배치하고, B를 직사각형의 오른쪽 아래에 최대한 배치하자. 그러면 A의 중심 좌표 E는 (r1,H-r1) / B의 중심 좌표 G는 (W-r2,r2). 두 원이 직사각형 안에 들어가려면 두 원의 중심 사이의 거리가 최소 (r1+r2)보다는 크거나 같아야 한다. (그림 링크)

: 일단 두 원 중 큰 원의 지름이 가로 길이, 세로 길이 중 최솟값보다 작거나 같아야 하고, 위 부등식을 만족하면 두 원을 직사각형에 넣기 가능!

import sys
input=sys.stdin.readline

while 1:
    H,W,r1,r2=map(int,input().split())
    if (H,W,r1,r2) == (0,0,0,0):
        break
    if min(H,W) >= max(2*r1,2*r2):
        if ((W-r1-r2)**2 + (H-r1-r2)**2) >= (r1+r2)**2:
            print('S')
        else:
            print('N')
    else:
        print('N')

---

★ 1500 최대 곱 ★

S,K=map(int,input().split())
ans=[S//K]*K
for x in range(S%K):
    ans[x]+=1
final = 1
for x in ans:
    final*=x
print(final)

 

🤽🏻‍♂️ 합이 일정하고, 주어진 숫자 개수가 일정한 상태에서, 산술-기하 평균에 의해 주어진 숫자가 서로 차이가 크지 않게 해야 best.

 

: maximizing product하기 위해 위 그림과 같이 산술-기하평균 식을 만들 수 있고, 등호 조건, 즉 x1~xk까지의 곱이 최댓값인 조건은 x1~xk가 모두 동일할 때, 즉 S/K일 때다, K가 정확히 S에 의해 나누어지지 않는다면, 정수들은 최대한 S/K에 가까워야 한다.

---