[기초-종합] 함께 문제 푸는 날(설명)
온라인 채점시스템에는 초등학생, 중고등학생, 대학생, 대학원생,
일반인, 군인, 프로그래머, 탑코더 등 아주 많은 사람들이 들어와 문제를 풀고 있는데,
실시간 채점 정보는 메뉴의 채점기록(Judge Status)을 통해 살펴볼 수 있다.
자! 여기서...잠깐..
같은 날 동시에 가입한 3명의 사람들이 온라인 채점시스템에 들어와 문제를 푸는 날짜가
매우 규칙적이라고 할 때, 다시 모두 함께 문제를 풀게 되는 그날은 언제일까?
예를 들어 3명이 같은 날 가입/등업하고, 각각 3일마다, 7일마다, 9일마다
한 번씩 들어온다면, 처음 가입하고 63일 만에 다시 3명이 함께 문제를 풀게 된다.
갑자기 힌트?
왠지 어려워 보이지 않는가?
수학에서 배운 최소공배수를 생각한 사람들도 있을 것이다. 하지만, 정보에서 배우고 경험하는
정보과학의 세상은 때때로 컴퓨터의 힘을 빌려 간단한 방법으로 해결할 수 있게 한다.
아래의 코드를 읽고 이해한 후 도전해 보자.
day는 날 수, a/b/c는 방문 주기이다.
...
day=1;
while(day%a!=0 || day%b!=0 || day%c!=0) day++; //이게 무슨 의미일까?
printf(＂%d＂, day);
...
물론, 아주 많은 다양한 방법이 있을 수 있다.
정보과학의 문제해결에 있어서 정답은?
하나가 아니라 주어진 시간/기억공간으로 정확한 결과를 얻을 수 있는 모든 방법이다.
따라서, 모든 문제들에는 정답이 하나뿐만이 아니다.
새로운, 더 빠른, 더 간단한 방법을 다양하게 생각해보고 도전해 볼 수 있다.
입력
같은 날 동시에 가입한 인원 3명이 규칙적으로 방문하는,
방문 주기가 공백을 두고 입력된다. (단, 입력값은 100이하의 자연수이다.)
출력
3명이 다시 모두 함께 방문해 문제를 풀어보는 날(동시 가입/등업 후 며칠 후?)을 출력한다.
입력 예시
3 7 9
출력 예시
63
풀이
days = list(map(int, input().split()))
def gcdi(a, b):
while (b != 0):
if (a > b):
a, b = b, (a % b)
else:
a, b = a, (b % a)
return a
def lcmu(a, b):
return a * b // gcdi(a, b)
def multi_lcmu(list):
while(len(list) != 1):
list.append(lcmu(list.pop(), list.pop()))
print(list.pop())
multi_lcmu(days)
설명
여러 숫자의 최소공배수 구하는 코드를 직접 짜보았습니다.
시행 착오가 많아서 https://brownbears.tistory.com/454 님의 코드를 많이 참고하였습니다.
한번에 모든 수의 최소공배수를 구하는 것이 아닌 2개의 숫자씩 뽑아서 구하는 방식입니다.
최대공약수를 구하는 방식은 유클리드 호제법을 참고하였습니다.
풀이 2
day1, day2, day3 = map(int, input().split())
day = 1
while((day % day1 != 0) or (day % day2 != 0) or (day % day3 != 0)):
day += 1
print(day)
설명
위의 문제에서 말하는 아주 다양한 방법 중 하나 이다.
or을 쓰게 되면 둘 중 하나가 True일 경우 True를 반환한다. 위 경우는 3개이기 때문에 셋 중 하나가 True이면 True를 반환한다.
세 개의 조건이 전부 False일 경우 False를 반환하게 되고 while을 빠져나오는 방식이고 day에 계속 1을 더해준 최종 값을 반환한다.
day % day1 != 0을 False로 만들기 위해서는 day값이 day1에 나누어 떨어져야 한다.
그렇게 되면 day % day1은 0이 나오게 되고
0 != 0 조건은 틀리게 되어 False를 반환하게 된다.
결국 각 모든 조건에서 False를 반환하기 위해서는 day1, day2, day3에 모두 나누어 떨어지는 숫자가 들어가게 되고
1부터 1씩 더하여 조건을 비교하므로 최솟값이 들어가게 되며 결국 day는 day1, day2, day3의 최소 공배수가 된다.