졍's 기술 블로그

약수

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 수학, 정수론

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

예제 입출력

Code

import sys
input = sys.stdin.readline

N = int(input())
aliquot = list(map(int, input().split()))

print(min(aliquot) * max(aliquot))

메모리: 30864 KB
시간: 68 ms

링

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 

문제

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

출력

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

예제 입출력

Algorithm

1. 첫 번째 숫자로 각 숫자의 최대공약수 구하기
2. 첫 번째 숫자 // 최대공약수, 두 번째 숫자 // 최대공약수 출력

Code

import sys
input = sys.stdin.readline

# 최대 공약수 구하는 함수
def euclid(A, B):
    # 나머지
    R = A % B
    
    # 두 수가 나누어 떨어지면 B Return
    if R == 0:
        return B
    else: # 나누어 떨어지지 않으면 재귀
        return euclid(B, R)

# 입력
N = int(input())
nums = list(map(int, input().split()))

for  i in range(1, len(nums)):
    answer = ''
    num = euclid(max(nums[0], nums[i]), min(nums[0], nums[i]))
    answer += str(nums[0]//num) + '/' + str(nums[i] // num)
    print(answer)

메모리: 30860 KB
시간: 72 ms

최대공약수와 최소공배수

티어 : Silver 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입출력

Algorithm

1. 유클리드 호제법 이용
    1.1. 유클리드 호제법 함수 생성 - 재귀
    1.2. A와 B의 최대 공약수는 B와 A%B의 최대공약수와 같다.
2. 최소공배수 = A*B%최대공약수

Code

import sys
input = sys.stdin.readline

def euclid(A, B):
    R = A % B
    # A가 B의 배수이면 Return
    if R == 0:
        return B
    return euclid(B, R)

A, B = map(int, input().split())
answer = euclid(max(A, B), min(A, B))
print(answer)
print(A * B // answer)

메모리: 30864 KB
시간: 72 ms