고동치는고동

문제 링크 : https://www.acmicpc.net/problem/14650 14650번: 걷다보니 신천역 삼 (Small) 욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 금강삼도 식후경, 걷다보니 신천역 삼, 그리고 특히 일�� www.acmicpc.net 먼저 특정 수에 대해 3의 배수인지 판별하는 방법을 알아보자. 각 자리수의 합이 3의 배수이면 3의 배수이다. 270, 999, 531, 8787의 경우를 보면 이 사실이 참임을 알 수 있다. 0, 1, 2를 이용해 구성하는 n자릿수의 경우의 수는 n-1자릿수의 경우에 3을 곱한 값이다. $$F_1 = 2$$ $$F_n = 3*F_{n-1}$$ ..

문제 링크 : https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 필요 알고리즘 : 유클리드 호제법 자연수 A와 B에 대해 A/B라는 분수가 있을 때 이를 기약분수로 형태로 변환하는 문제이다. 두개의 입력되는 분수에 대하여 A와 B를 구하는 방법은 쉽다. 그러나 A/B꼴의 분수를 기약분수로 변환하는 과정에서 문제가 생긴다. 기약분수로 변환하기 위해서는 먼저 A와 B의 최대공약수를 구해야된다. 기존의 방법으로 최대공약수를 구하기 위해서는 min(A, B) 횟수 만큼의 연산이 수행되어야 한다. 입력되는 ..