★Math & Geometry Intermediate I - 13 Solved★

★ 1676 팩토리얼 0의 개수 ★

 

🧘🏼‍♂️ 뒤에서부터 거꾸로 일일이 0의 개수를 문제대로 찾는 brute-force

N = int(input())
fac = 1
for i in range(N, 0, -1):
    fac *= i

cnt = 0
for num in str(fac)[::-1]:
    if num == '0':
        cnt += 1   
    else:
        break
print(cnt)

 

🧘🏼‍♂️ 그러나, 수학적으로 접근해서 brute-force가 아닌 수학 풀이로 시간을 더 단축하자면,

 

🧘🏼‍♂️ 팩토리얼 결과 끝의 0의 개수 → 10으로 나누어지는 횟수의 개수 → 5와 2의 개수 → 5의 개수

① 10으로 나누어떨어진다면 끝에 0이 1개, 100으로 나누어떨어진다면 끝에 0이 2개, 즉 끝의 0의 개수는 10으로 나누어지는 횟수의 개수

② 10은 2*5로 구성되므로, 2와 5를 쌍으로 한 개수가 몇 개인지를 뜻함

③ 2는 5에 비해 무수히 많으므로 우리는 5의 개수만 구하면 됨

④ 즉, 5를 곱하면 끝에 0이 1개 증가, 10을 곱하면 0이 2개 증가, ~ 그러나 5의 제곱수의 배수 - 25의 배수, 125의 배수 등등을 곱하면, 곱할 때 5가 각각 2번, 3번이나 곱해지므로 5의 제곱수 배수만 주의 (625부터는 문제 조건 N <= 500에 의해 상관없음)

 

🧘🏼‍♂️ 알고리즘 흐름

① 5로 나눈 몫 더하기 (딱 5가 1번 곱해지는 횟수 카운트)

② 25로 나눈 몫 더하기 (25 배수는 5가 최소 2번 이상 있고, 위 ①에서 5카운트 했으므로 25가 1번 곱해지는 횟수만 카운트)

③ 125로 나눈 몫 더하기 (마찬가지로 125가 1번 곱해지는 횟수만 카운트)

④ 625로 나눈 몫 더하기 ~~ 등등 (문제에선 500까지이므로 적용 x)

N=int(input())
print(N//5+N//25+N//125)

 

🧘🏼‍♂️ 알고리즘 흐름 → 일반화

→ 5 - 25 - 125 - 625 ~ 5의 제곱수가 이전 제곱수의 5배인 성질을 이용한다

ex) 예를 들어 5로 나눈 몫이 0이 아니라면, 해당 몫에 5를 또 나눈 몫이 0아닐 경우 25이상임을 뜻한다. 이 성질을 이용해 아래와 같이 while문 작성 가능

N=int(input())
cnt=0
while N>4:
    cnt+=N//5
    N//=5
print(cnt)

---

★ 24313 알고리즘 수업 - 점근적 표기 1 ★

 

a1, a0 = map(int, input().split())
c = int(input())
n0 = int(input())

if a1 == c:    
    if -100<= a0 <= 0:
        print(1)
    
    else:
        print(0)

elif a1 < c:
    if n0 >= (a0/(c-a1)):
        print(1)

    else:
        print(0)

else:
    print(0)

 

🧘🏼‍♂️ 특정상황에서 O-표기법을 만족하는 지 묻는 문제이다.

① f(n) = a1n + a0 (0<=|ai|<=100)

② g(n) = n

 

🧘🏼‍♂️ a1,a0,c가 모두 주어진 상태에서 부등식을 정리하면 n(c-a1)>=a0

 

🧘🏼‍♂️

① c = a1 → a0<=0일 경우 O-표기법을 만족해서 1 아니면 0

 

② c > a1 

→ 부등호를 정리하면 n<=(a0/(c-a1))

→ n<=n0를 만족해야 하므로 (a0/(c-a1))>=n0이면 O-표기법을 만족해서 1, 아니면 0

 

③ c < a1

→ 위 ②와 부등호가 반대방향으로 되므로 n0보다 큰 모든 n이 만족할 수 없음. 따라서 오로지 0만 가능

---

★ 24314 알고리즘 수업 - 점근적 표기 2 ★

 

a1,a0=map(int, input().split())
c=int(input())
n0=int(input())

if a1==c:
    if a0>=0:print(1)
    else:print(0)

elif a1>c:
    if n0>=(a0/(c-a1)):print(1)
    else:print(0)

else:print(0)

 

※ 위 24313 문제와 부등호 방향만 바뀜 ※

---

★ 1193 분수찾기 ★

 

X=int(input())
num=(((8*X+1)**(1/2)-1)/2)
if num==int(num):
    n = int(num -1)
else:
    n = int(num)
order=X-((n)*(n+1)//2)
if (n+2)%2==0:
    print(str(n+2-order)+'/'+str(order))
else:
    print(str(order)+'/'+str(n+2-order))

 

🧘🏼‍♂️

① 대각선 방향으로 분수 + 분자의 합이 1 → 2 → 3 → 4 형태로 커지는 규칙을 사용

② 앞선 모든 대각선 방향의 개수를 n이라 하면

 

→ if문으로 num으로 위 부등식의 n 값을 구한다.

 

🧘🏼‍♂️그렇다면 대각선 방향의 일정한 분자+분모의 합은 n+2

 

③ 분자+분모의 합이 짝수인지 홀수인지에 따라 결과 출력하면 끝!

 

🧘🏼‍♂️다른 풀이

X=int(input())
num_of_diagonal_lines=1
cum_num_of_diagonal_lines=1
before_cum_num_of_diagonal_lines=0
while cum_num_of_diagonal_lines < X:
    before_cum_num_of_diagonal_lines=cum_num_of_diagonal_lines
    cum_num_of_diagonal_lines+=(num_of_diagonal_lines+1)
    num_of_diagonal_lines+=1
order = X -before_cum_num_of_diagonal_lines
total=num_of_diagonal_lines+1
if total%2==1:
    print(f'{order}/{total-order}')
else:
    print(f'{total-order}/{order}')

 

→ 직접 대각선 개수를 누적으로 더한 것과 / 현재 대각선의 개수를 while문으로 업데이트하며 최종적으로 order와 total을 구하고 바로 출력!

→ 누적으로 더해가는 add up하는 여러 변수를 while문으로 update한다는 점 주의!

---

★ 13345 Completing the Square ★

 

ax,ay=map(int,input().split())
bx,by=map(int,input().split())
cx,cy=map(int,input().split())

d1,d2,d3=(ax-bx)**2+(ay-by)**2,(ax-cx)**2+(ay-cy)**2,(bx-cx)**2+(by-cy)**2

if d1>d2: #max d1
    print(ax+bx-cx,ay+by-cy)
elif d2>d3: #max d2
    print(ax+cx-bx,ay+cy-by)
else: #max d3
    print(cx+bx-ax,cy+by-ay)

 

🧘🏼‍♂️ 정사각형의 세 꼭지점의 좌표가 주어진 상태에서 나머지 꼭지점의 x, y 출력 문제. 세 꼭지점간의 거리를 구한 후, 최대 거리에 있는 두 점이 정사각형의 대각선을 이루는 두 점이므로, 두 점의 합에 나머지 꼭지점을 뺀 좌표가 출력하고자 하는 x, y

: 정사각형의 세 꼭지점의 좌표만 알면 두 대각선의 중점은 일치한다는 성질을 이용해 나머지 한 꼭지점의 좌표는 위와 같이 알 수 있다. 

---

★ 15803 PLAYERJINAH'S BOTTLEGROUNDS ★

coordinates=[]
for _  in range(3):
    x,y=map(int,input().split())
    coordinates.append((x,y))

one,two,three=coordinates[0],coordinates[1],coordinates[2]
if (two[0]!=one[0]) and (three[0]!=one[0]) and (two[0]!=three[0]):
    s1,s2,s3=(two[1]-one[1])/(two[0]-one[0]),(three[1]-one[1])/(three[0]-one[0]),(three[1]-two[1])/(three[0]-two[0])
    if s1==s2==s3:
        print('WHERE IS MY CHICKEN?')
    else:
        print('WINNER WINNER CHICKEN DINNER!')
else:
    a,b,c=one[0],two[0],three[0]
    if len(set([a,b,c])) == 1:
        print('WHERE IS MY CHICKEN?')
    else:
        print('WINNER WINNER CHICKEN DINNER!')

 

🧘🏼‍♂️ 세 점이 한 직선을 이루는 지 알아보는 유형. A,B,C 세 점이 있다면 A와 B를 잇는 직선의 기울기, B와 C를 잇는 직선의 기울기, A와 C를 잇는 직선의 기울기 총 3개의 기울기가 모두 동일하면 한 직선. 동일하지 않다면 한 직선에 있지 않다고 말할 수 있다. 이 때, 기울기를 구할 때 분모가 0이 되는 경우만 주의. 분모가 0이 될 경우, 즉 세 점 중 x좌표가 동일한 쌍이 존재할 경우, 세 점의 x좌표가 모두 동일한 경우만 직선. 아닌 경우는 직선 x

---

★ 1358 하키 ★

import sys
input=sys.stdin.readline

W,H,X,Y,P=map(int,input().split())
ans=0
for _ in range(P):
    x,y=map(int,input().split())
    if X<=x<=X+W and Y<=y<=Y+H:
        ans+=1
    else:
        #centers of circles each: (X,Y+H/2) (X+W,Y+H/2)
        if ((x-X)**2 + (y-(Y+(H/2)))**2)<=(H/2)**2:
            ans+=1
        else:
            if ((x-(X+W))**2 + (y-(Y+(H/2)))**2)<=(H/2)**2:
                ans+=1

print(ans)

 

🧘🏼‍♂️ 주어진 점이 직사각형에 있는 지의 여부는 (x,y)의 x가 X와 X+W 사이, y가 Y와 Y+H 사이에 있는 지 확인

 

🧘🏼‍♂️ 원 안에 있는 지의 여부는 (x,y)가 각 원의 중심과의 거리가 반지름 이하인지 확인

---

★ 1064 평행사변형 ★

 

import sys
xa,ya,xb,yb,xc,yc=map(int,input().split())
AB=((xb-xa)**2+(yb-ya)**2)**(1/2)
BC=((xb-xc)**2+(yb-yc)**2)**(1/2)
AC=((xc-xa)**2+(yc-ya)**2)**(1/2)
#check if 3 aligned in one line
if xa==xb==xc:
    print(-1)
    sys.exit()
elif ya==yb==yc:
    print(-1)
    sys.exit()
else:
    if xa==xb:
        slope1=0
    else:
        slope1=(ya-yb)/(xa-xb)
    if xc==xb:
        slope2=0
    else:
        slope2=(yc-yb)/(xc-xb)
    if slope1==slope2:
        print(-1)
        sys.exit()
    else:
        print(max(AB*2+BC*2,BC*2+AC*2,AB*2+AC*2)-min(AB*2+BC*2,BC*2+AC*2,AB*2+AC*2))

 

🧘🏼‍♂️ 평행사변형을 이루지 않는 경우만 생각해주면 된다. 세 점이 모두 일직선을 이루는 경우는 평행사변형이 될 수 없다. 이 때 세 점이 모두 y축에 있는 경우 / 모두 x축에 있는 경우 / 해당 두 케이스가 아닌 일직선에 있는 경우 각각 판별

 

🧘🏼‍♂️ 세 점이 모두 일직선에 있지 않다면 평행사변형을 만들 수 있으므로, 세 개의 점을 A,B,C라고 했을 때 만들 수 있는 평행사변형은 (1) AB,BC를 변으로 / (2) AB, AC를 변으로 / (3) BC,AC를 변으로 하는 세 개의 case, 선분 길이 공식으로 구해 최댓값, 최솟값 차이 바로 출력하면 끝

---

★ 1748 수 이어 쓰기 1 ★

N=input()
l=len(N)
ans=0
start=9
for i in range(1,l):
    ans+=start*i
    start*=10
if l!=1:
    remain=int(N)-9*(int('1'*(l-1)))
    print(ans+remain*(l))
else:
    print(int(N))

 

🧘🏼‍♂️ 입력한 N의 자리수를 l이라 한다면 l-1까지의 앞자리 모든 수를 더하고, l자리 수는 남은 숫자만큼만 곱해줘서 최종적으로 더해주면 끝.

---

★ 30002 Joon Paberil ★

N=int(input())

near=int(N**(1/2))**2
if near%2==0:
    start=(1,int(near**(1/2))+1)
else:
    start=(int(near**(1/2))+1,1)

diff=N-near
if diff <= near**(1/2):
    if near%2==0:
        print(start[0]+diff,start[1])
    else:
        print(start[0],start[1]+diff)
else:
    if near%2==0:
        print(1+int(near**(1/2)),start[1]-(diff-int(near**(1/2))))
    else:
        print(start[0]-(diff-int(near**(1/2))),1+int(near**(1/2)))

 

🧘🏼‍♂️ 규칙성을 확인하고, 입력한 N이라는 숫자가 존재하는 가장 큰 정사각형의 크기를 먼저 near로 확인. near가 홀수 / 짝수에 따라 각각 시작하는 start 번호 확인. 그리고 차이 diff가 near의 전반부인지 후반부인지에 따라 분기 나누어서 수학 규칙성 찾고 코드 작성. 규칙만 찾으면 된다.

---

★ 30020 치즈버거 만들기 2 ★

import sys
input=sys.stdin.readline

A,B=map(int,input().split())

if A<=B:print('NO')
else:
    diff=A-B
    if diff>B:print('NO')
    else:
        print('YES')
        print(diff)
        for i in range(diff):
            if i != (diff-1):
                print('aba')
            else:
                b_cnt=(B-(diff-1))
                print('ab'*b_cnt+'a')

 

🧘🏼‍♂️ 한 개의 치즈버거를 만들 때 패티의 개수를 a, 치즈의 개수를 b라 하면 무조건 a = b + 1이어야 한다. 따라서 A(a의 합)와 B(b의 합)을 보면, A-B가 곧 만들 수 있는 치즈버거의 개수. 만약, B>=A이거나, A-B인 만들 수 있는 치즈버거의 개수가 치즈의 개수인 B보다 크다면, 이는 곧 A-B개의 치즈버거에 각각 치즈 1개씩을 넣을 수 없다는 뜻이다. 따라서 해당 경우를 제외하고 diff-1개수만큼 aba를 만들고, 나머지 1개는 남은 b count로 b를 구성하고 a를 앞뒤에 넣어서 치즈버거를 만들 수 있다. (가능한 경우 아무거나 출력 가능하므로)

---

★ 9471 피사노 주기 ★

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    N,M=map(int,input().split()) #M>=2
    bef1,bef2 = 1,1
    for i in range(M**2):
        cur = (bef1+bef2)%M
        if bef2==cur==1:
            print(N,i+1)
            break
        else:
            bef1=bef2
            bef2=cur

 

🧘🏼‍♂️ 피보나치 수열에서 mod m을 진행했을 때, 모든 mod m으로 진행한 나머지는 규칙 주기성을 갖는다(피사노 주기 성질). 따라서 맨 앞의 mod m 결과 1 1은 언젠가 무조건 똑같이 진행되며, 브루트포스로 1 1이 또 나왔을 때까지의 주기를 구해서 출력하면 된다. mod m에서 바로 앞과 현재의 mod m 순서쌍 가능 개수는 비둘기 집의 원리(0 ~ m-1 (mod m)이 앞과 현재 가능 개수, 즉 m*m으로 m^2)에 의해 최대 m^2이므로 m^2까지만 돌리면 된다.

---

★ 2740 행렬 곱셈 ★

 

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
A=[]
for _ in range(N):
    A.append(list(map(int,input().split())))
B=[]
M,K=map(int,input().split())
for _ in range(M):
    B.append(list(map(int,input().split())))

ans=[]

for i in range(N):
    ans=[]
    for k in range(K):
        n=0
        for j in range(M):
            n+=(A[i][j]*B[j][k])
        ans.append(n)
    print(*ans)

 

🧘🏼‍♂️ NxM 행렬과 MxK 행렬의 곱 결과는 NxK 행렬로 나온다. 따라서 for i in range(N)으로 돌리고, for k in range(K)로 돌린 다음, 중간 숫자 for j in range(M)을 돌리면 된다. 아래 행렬 곱 그림 참조

 

🧘🏼‍♂️

(1) i가 0일때부터 N-1일 때까지, 첫번째 행렬의 행을 위에서부터 돈다.

(2) 첫번째 행렬의 특정 i행일 때, 두번째 행렬의 첫번째 열부터 마지막 열까지 돈다(k가 0일때부터 k-1일때까지)

(3) 즉, 첫번째 행렬의 특정 i행(N)일 때 & 두번째 행렬의 특정 k열(K)일 때: i행의 m번째 원소와 k열의 m번째 원소를 서로 곱해나간 합을 결과 행렬의 원소로 배치

 

🧘🏼‍♂️ 행렬 곱 코드 작성 시, NxM 행렬과 MxK행렬 곱 형태는 첫번째 행렬의 행과 두번째 행렬의 열을 돌면서(이중 반복문), M개의 곱 합을 (삼중 반복문) 새로운 행렬의 원소로 만들면 된다.

---