TIL 코딩공장

20240419 백준 파이썬 공부
2485번 가로수

1. 문제
직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. 
KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. 
KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 
가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 
또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 
모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 
단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

2. 입력
첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 
둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 
가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 
가로수의 위치를 나타내는 정수는 모두 다르고, 
N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

3. 출력
모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

>>>코드

import sys
# 최소공배수 구하는 함수
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
# n 입력받기
n = int(input())
tree, inter = [], []
# 나무들의 위치 입력받기
for _ in range(n):
    tree.append(int(sys.stdin.readline().strip()))
# 각각 나무 간의 간격 구하기
for i in range(1, n):
    inter.append(tree[i]-tree[i-1])
# 각 간격들 사이의 최대공약수 구하기
inter.sort(reverse = True)
g = inter[0]
for i in range(1, n-1):
    g = gcd(g, inter[i])
t = (tree[-1] - tree[0]) // g + 1
print(t - n)

>>>문제링크
https://www.acmicpc.net/problem/2485

20240418 백준 파이썬 공부
1735번 분수 합

1. 문제
분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.

두 분수의 합 또한 분수로 표현할 수 있다. 
두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 
기약분수란 더 이상 약분되지 않는 분수를 의미한다.

2. 입력
첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 
입력되는 네 자연수는 모두 30,000 이하이다.

3. 출력
첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.

>>>코드

# 최대공약수 구하기
def gcd(a, b):
    while b>0:
        a, b = b, a%b
    return a

s1, m1 = map(int, input().split()) # 첫번째 분수
s2, m2 = map(int, input().split()) # 두번째 분수
m = m1 * m2 // gcd(m1, m2) # 분모 = 각 분모의 최소공배수
s = s1 * (m2//gcd(m1, m2)) + s2 * (m1//gcd(m1, m2)) # 분자합 = 분자 * (다른 분모 / 분모 최대공약수)의 합 
s, m = s // gcd(s, m), m // gcd(s, m) # 기약분수 만들기(분자, 분모의 최대공약수로 나누기)
print(s, m)

>>>문제링크
https://www.acmicpc.net/problem/1735

20240417 백준 파이썬 공부
13241번 최소공배수

1. 문제
정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.

예:
- 10은 5의 배수이다 (5*2 = 10)
- 10은 10의 배수이다(10*1 = 10)
- 6은 1의 배수이다(1*6 = 6)
- 20은 1, 2, 4,5,10,20의 배수이다.

다른 예:
- 2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
- 10과 20의 최소공배수는 20이다.
- 5와 3의 최소공배수는 15이다.

당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.

2. 입력
한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.

50%의 입력 중 A와 B는 1000(103)보다 작다. 
다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다.

추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. 
C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.

3. 출력
A와 B의 최소공배수를 한 줄에 출력한다.

>>>코드

n, m = map(int, input().split())
def gcd(n, m):
    while m>0:
        n, m = m, n%m
    return n
print(n*m//gcd(n,m))

>>>문제링크
https://www.acmicpc.net/problem/13241

20240416 백준 파이썬 공부
1934번 최소공배수

1. 문제
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 
이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 
예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 
둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

3. 출력
첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

>>>코드

def num(a, b):
    while b != 0:
        a, b = b, a%b
    return a

for _ in range(int(input())):
    a, b = map(int, input().split())
    print(a * b // num(a, b))

>>> 최대공약수 구하기: 유클리드 호제법
a와 b의 최대 공약수는
b와 a%b의 최대 공약수와 동일하다

>>> 최소공배수 = a * b / 최대공약수

>>>문제링크
https://www.acmicpc.net/problem/1934