알고리즘 마라톤 3일차

13번

영화감독 숌

기냥 무식하게 1식 늘리면서 '666'이 포함되어 있는지 확인하는 브루스 포스 문제

count = int(input())
end_num = 666
while True:
    if '666' in str(end_num):
        count -= 1
        if count == 0:
            break
    end_num += 1
print(end_num)

14번

달팽이는 올라가고 싶다

시간 초과 코드

A, B, V = map(int, input().split())
count = 0
while True:
    count += 1
    V = V - A
    print(V)
    if V <= 0:
        break
    else:
        V = V + B
print(count)

a,b,v = map(int,input().split())
k = 0	# 올라가는 데 걸리는 일수
d = 0	# 올라간 높이
while 1:
    k+=1
    if a*k-b*(k-1)>=v:
        break
print(k)

여기서 if 문을 k만 남도록 정리하면 k >= (v-b) / (a-b)가 된다.

a,b,v = map(int,input().split())
k = (v-b)/(a-b)
print(int(k) if k == int(k) else int(k)+1)	#삼항연산자

답이 둘 중 하나인 이유는 분수가 나누어 떨어지지 않는 경우는 하루가 더 걸리는 거나 마찬가지이기 때문이다. (4.1일은 결국 5일이니까)

15번

약수

약수가 모두 주어지기 때문에 가장 작은 약수와 가장 큰 약수를 곱하면 진짜 수를 구할 수 있다.

cnt = int(input())
aliquot_list = list(map(int, input().split()))
max_num = max(aliquot_list)
min_num = min(aliquot_list)
print(max_num * min_num)

16번

최대공약수와 최소공배수

유클리드 호제법을 알면 간단해진다.
두 수의 최대공약수는 두 수 중 작은 수와 두 수 중 큰 수에서 작은 수를 나눈 나머지의 최대공약수와 같다.
gcd(24, 18) = gcd(18, 6) = gcd(6, 0) 에서 작은 수가 0이 되는 순간의 큰 수가 바로 최대공약수다.
최대공약수를 구하면 최소공배수는 두 수를 곱한 값을 최대공약수로 나누어주면 끝이다.

a, b = map(int, input().split())

def gcd(x, y):
    mod = x % y
    while mod > 0:
        x = y
        y = mod
        mod = x % y
    return y

def lcm(x, y):
    return x * y // gcd(x, y)

print(gcd(a, b))
print(lcm(a, b))

17번

ACM 호텔

case = int(input())
for i in range(case):
    h, w, n = map(int, input().split())
    ho = n // h + 1
    floor = n % h
    if n % h == 0:
        ho = n // h
        floor = h
    print(str(floor * 100 + ho))

18번

소수 구하기

import math

m, n = map(int, input().split())

def isPrime(num):
    if num == 1:
        return False
    else:
        # n = int(math.sqrt(num))
        n = int(num**0.5)
        for i in range(2, n+1):
            if num % i == 0:
                return False
        return True

for i in range(m, n+1):
    if isPrime(i):
        print(i)

19번

하노이 탑 이동 순서

재귀 문제다. 가장 단순한 2개의 원판을 가지고 생각해보면 맨 위의 원판이 두 번째 보조 기둥으로 이동하고, 그 다음 첫 번째 시작 기둥에 남은 원판이 세 번째 목표 기둥으로 이동한 뒤, 보조 기둥에 위치한 원판을 세 번째 목표 기둥으로 옮기면 끝이 난다. 이게 한 사이클이다.
정리하면, 1 -> 2, 1 -> 3, 2 -> 3 사이클이다.
여기서 원판의 갯수만 점점 늘어나는 것 뿐이다.

자 이제 함수 호출 순서를 따져보면
입력 : hanoi(2, 1, 3)
hanoi(1, 1, 2) → print(1, 2)
print(1, 3)
hanoi(1, 2, 3) → print(2, 3)

이게 끝이다.

disk = int(input())
def hanoi(disk, a, b):
    if disk > 1:
        hanoi(disk-1, a, 6-a-b) # 보조 기둥으로 옮기기

    print(a, b) # 목표 기둥으로 옮기기

    if disk > 1:
        hanoi(disk-1, 6-a-b, b) # 보조 기둥에서 목표 기둥으로 옮기기

print(2 ** disk-1) # 총 이동 횟수
hanoi(disk, 1, 3) # 3개의 원판을 기둥 1에서 기둥 3으로 옮기겠다.

20번

좌표 정렬하기 2

람다식을 이용하면 간단해진다. 람다식은 별도로 공부를 좀 해야겠다.

dot_cnt = int(input())
dot_list = []
for i in range(dot_cnt):
    dot_list.append(list(map(int, input().split())))
dot_list.sort(key=lambda x: (x[1], x[0]))
# print(dot_list)
for i in dot_list:
    print(i[0], i[1])