[기초-종합] 함께 문제 푸는 날

문제 설명

koistudy.net 에는

초등학생, 중학생, 고등학생, 대학생, 대학원생, 일반인, 군인, 프로그래머, 탑코더  등 아주 많은 사람들이 들어와 문제를 풀고 있는데, 가입하고 Guest Board를 통해 정회원으로 등업이 되어야 문제를 풀어볼 수 있다.


매 시간의 실시간 채점 정보는 메뉴의 Judge Status 를 통해 살펴볼 수 있다.


자! 여기서...잠깐..

같은 날 동시에 가입한 3명의 사람들이 koistudy.net을 들어와 문제를 푸는 날짜가

매우 규칙적이라고 할 때,


다시 모두 함께 문제를 풀게 되는 그날은 언제일까?

예를 들어 3명이 같은날 가입/등업하고, 각각 3일 마다, 7일 마다, 9일 마다 한 번씩 들어온다면, 처음 가입하고 63일 만에 다시 3명이 함께 문제를 풀게 된다.

입력

같은 날 동시에 가입한 인원 3명이 규칙적으로 방문하는, 방문 주기가 공백을 두고 입력된다.

 (단, 입력값은 100이하의 자연수이다.)

출력

3명이 다시 모두 함께 방문에 문제를 풀어보는 날(동시 가입/등업 후 며칠 후?) 을 출력한다.

입력 예시

3 7 9

출력 예시

63

도움말

이 문제를 수학에서 배운 최소 공배수로 풀 수도 있고 그게 귀찮다면 아래 코드처럼 전수 조사를 할수도 있다.


day는 날 수, a/b/c는 방문 주기이다.
...
day=1;
while(day%a!=0 || day%b!=0 || day%c!=0) day++; //이게 무슨 의미일까?
printf("%d", day);
...


물론, 아주 많은 다양한 방법이 있을 수 있다.

informatics의 문제 해결에 정답은 하나가 아니라...

지정된 시간내에 정확한 결과를 얻을 수 있는 모든 방법이 정답이다.


따라서, 모든 문제들에는 정답이 하나 뿐 만이 아니다.


새로운, 더 빠른, 더 간단한 방법을 다양하게 생각해보고 도전해 보기 바란다.

참고로 최소공배수를 구하는 알고리즘은 유클리드의 호제법을 써서 최대공약수를 구하면 간단히 구할 수 있다.

유클리드 호제법은 다음과 같다.

 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. [출처:위키백과]

최소공배수는 두 수를 곱하고 두 수의 최소공배수로 나누면 된다.

#include <stdio.h>

int main(){

    int a, b, c, day=1;

    scanf("%d %d %d",&a,&b,&c);

    while(day%a!=0 || day%b!=0 || day%c!=0)  day++;

    printf("%d\n", day);

    return 0;

}

a, b, c=input().split()

a, b, c=int(a), int(b), int(c)

 

d = 1

while(d % x != 0 or d % y != 0 or d % z != 0):

    d += 1

 

print(d)

또는

def gcd(m,n):

    while(n != 0):    

       temp = m % n

       m, n = n, temp

    return abs(m)

a, b, c=input().split()

a, b, c=int(a), int(b), int(c)

x = a * b / gcd(a, b)

y = x * c / gcd(x, c) 

print(int(y))