밑의 링크는 CodeUp에서의 문제 링크입니다.
문제는 링크를 통해서 직접 봐주시길 바랍니다.
바이러스 백신
$10$은 세 가지 바이러스 감염을 모두 예방할 수 있으며 가장 큰 값이다.
codeup.kr
주의해야 할 점
1. map, split를 사용하는 입력 방식
실수나 정수인 여러 값들이 입력값일 때,
split 메서드를 사용해 공백이나 어떤 문자를 기준으로 입력값을 여러 값들로 분리하고,
map 내장 함수로 각각의 값들을 int형이나 float형으로 정수, 실수 자료형으로
변환하는 기법은 매우 많이 쓰입니다.
코드 이해부터 하고 나면 다른 문제에서도 외운 듯이 사용해봅시다.
nums = map(int, sys.stdin.readline().split())
2. 최대공약수를 구하는 방법
최대공약수를 구하는 알고리즘으로는 유클리드 호제법이 있습니다.
저도 이번 문제를 풀 때 유클리드 호제법을 사용해서 최대공약수를 구했습니다.
그런데 파이썬에서는 math 모듈에 매개변수를 넣으면 최대공약수를 반환하는 gcd 함수가 있습니다.
밑의 링크는 gcd 함수에 대해서 제가 포스팅한 내용이니 한 번 읽어보세요.
그리고 유클리드 호제법으로 이 문제를 풀었으면 gcd 함수도 이용해서 한 번 풀어보세요.
정말 간단합니다.
[Python] gcd 함수 : 최대공약수
알고리즘 문제들을 풀다 보면 누구나 한 번쯤은 최대공약수, 최소공배수를 구해야 되는 문제를 만날 것입니다. 최대공약수와 최소공배수를 구하기 위해 사용하는 알고리즘으로 유클리드 호제
brightnightsky77.tistory.com
3. 세 숫자의 최대공약수
수학에서 최대공약수를 구할 때는 보통 두 숫자의 최대공약수를 구하는데
이 문제에서는 숫자 3개의 최대공약수를 구해야 합니다.
그런데 그리 특별한 방법이 있는 것은 아니고
먼저 두 숫자의 최대공약수를 구하고 그 최대공약수와 나머지 한 숫자와의 최대공약수를 구하면
세 숫자의 최대공약수입니다.
예제 설명
1. 첫 번째 예제
- 입력
10 20 30
- 출력
10
- 설명
1 ~ 3000의 정수인 오름차순으로 입력한 세 바이러스 번호들은 각각 10, 20, 30입니다.
세 바이러스 번호의 감염을 예방할 수 있는 가장 값싼 백신 번호는
세 바이러스 번호의 최대공약수입니다.
10, 20, 30의 최대공약수는 10이므로 10을 출력합니다.
생각한 풀이 과정
문제를 읽고 나면 가장 값싼 백신의 번호는 3개의 바이러스 번호의 최대공약수를 구하는 것입니다.
숫자 3개의 최대공약수는 구하는 방법은 먼저 두 숫자의 최대공약수를 구하고
그 최대공약수와 나머지 한 숫자의 최대공약수를 구하는 것입니다.
그래서 먼저 매개변수로 두 숫자를 받으면
유클리드 호제법을 이용해 최대공약수를 반환하는 함수를 만들어줍니다.
def vaccine(num1, num2):
while num2 != 0:
num1, num2 = num2, num1 % num2
return num1
1 ~ 3000인 3개의 바이러스 번호를 오름차순으로 공백으로 구분해 입력합니다.
각각 int형으로 변환하고 변수에 저장합니다.
virus1, virus2, virus3 = map(int, stdin.readline().split())
3개의 바이러스 번호의 가장 값싼 백신의 번호인 최대공약수를 구합니다.
virus1_2_vaccine = vaccine(virus1, virus2)
cheapest_vaccine = vaccine(virus1_2_vaccine, virus3)
가장 값싼 백신의 번호를 출력합니다.
print(cheapest_vaccine)
제출한 파이썬 코드
# readline을 사용하기 위해 import합니다.
from sys import stdin
# 두 바이러스 번호를 넣었을 때 가장 값싼 백신 번호를 반환하는 함수를 선언합니다.
# 가장 값싼 백신 번호는 두 바이러스 번호의 최대공약수입니다.
def vaccine(num1, num2):
# 유클리드 호제법을 사용해서 두 숫자의 최대공약수를 구해줍니다.
# num2의 값이 0이 아니면 계속 반복합니다.
while num2 != 0:
# num2의 값은 변수 num1에, num1의 값을 num2의 값으로 나누어 나온 나머지를 변수 num2에 저장합니다.
num1, num2 = num2, num1 % num2
# 두 숫자의 최대공약수인 num1의 값을 반환합니다.
return num1
# 3개의 바이러스 번호를 오름차순으로 공백으로 구분해 입력합니다.
# 1 ~ 3000의 정수입니다.
# 각각 int형으로 변환합니다.
virus1, virus2, virus3 = map(int, stdin.readline().split())
# virus1, virus2의 가장 값싼 백신 번호를 구해 변수 virus1_2_vaccine에 저장합니다.
virus1_2_vaccine = vaccine(virus1, virus2)
# virus1_2_vaccine, virus3의 가장 값싼 백신 번호를 구해 변수 cheapest_vaccine에 저장합니다.
cheapest_vaccine = vaccine(virus1_2_vaccine, virus3)
# 세 바이러스의 가장 값싼 백신 번호를 출력합니다.
print(cheapest_vaccine)
제출 결과
댓글