공작소

>> 문제 바로가기 (https://www.acmicpc.net/problem/29196) 문제 이 대회의 운영진 중 한 명인 KSA 학생은 얼마 전 소수 공포증을 극복했으나 또 다른 소수를 구별할 수 없게 되어 버렸다. KSA의 명예를 지키기 위해 어떤 소수 k를 입력받아 k를 나타내는 분수 p/q를 아무거나 구해주자. p와 q는 10^9 이하인 양의 정수이며, k와 p/q의 절대오차 또는 상대오차가 10^(−6) 이하면 정답이다. 입력 첫 번째 줄에 소수 k가 주어진다. 출력 첫 번째 줄에 조건을 만족하는 분수가 존재한다면 YES, 아니라면 NO를 출력한다. 만약 그러한 분수가 존재한다면, 두 번째 줄에 두 정수 p, q를 공백을 사이에 두고 출력한다. 정답이 여러 개 존재한다면 그중 아무거나 출력해..

문제 이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 1번부터 N번까지 심었다. 이 나무들의 초기 높이는 모두 0이다. 사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 2개를 준비했다. 한 물뿌리개는 나무 하나를 1만큼 성장시키고, 다른 물뿌리개는 나무 하나를 2만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 3만큼 키울 수도 있다. 물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다. 그 순간, 갊자가 놀러와서 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다고 말했다. 이제 이하는 약간 걱정이 되기 시작했는데, 갊자가 알려준 사과나무의 배치를 이 프로그램 상으로 만들어내지..

문제 계산은 사람에게나 컴퓨터에게나 상당히 번거로운 일인 것 같다. 특히 n개의 행렬 M1,M2,⋯,Mn의 곱, 즉 M1M2⋯Mn같은 것은 정말이지 계산하기 귀찮다. 행렬과 그 곱셈이 익숙하지 않은 사람들을 위해 설명을 해 보자면, 먼저 행렬은 여러 수나 기호, 문자, 수식 같은 것을 직사각형 모양으로 적절히 배열한 후 이를 괄호로 묶은 것을 말한다. 편의상 이 문제에서는 행렬에 정수만 배열한다고 가정한다. 예를 들어 아래와 같은 것이 행렬의 한 예이다. 행렬에 배열된 수를 성분이라고 한다. 행렬의 가로줄은 행이라고 부르며, 위에서부터 차례로 제1행, 제2행, 제3행, … 식으로 이름을 붙인다. 또한 행렬의 세로줄은 열이라고 부르며, 왼쪽에서부터 차례로 제1열, 제2열, 제3열, … 식으로 이름을 붙인다..

문제 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 ..

문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. 풀이 과정 각 자리가 등차수열을 이루어야 한다고 하고, 1보다 크거나 같고 N (최대 1,000)보다 작거나 같은 한수의 개수를 출력해야 한다고 한다. 일단 구해야 하는 것을 알아보도록 하자. 한수는 해당 수의 각 자리 수가 등차수열을 이룰 때 한수라고 한다고 한다. 즉, 1부터 99까지 (숫자가 한 자리 수..

문제 The Ultimate Binary Watch is a maker project that uses small LEDs to display time on a watch face. The display uses four columns of four LEDs each, with each column representing one digit of the current time in hours and minutes. Time is displayed in 24-hour format, with the 1st (left-most) column displaying the tens position for hours, the 2nd column displaying the ones position for hours, t..

문제 2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오. 입력 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 주어진 수를 8진수로 변환하여 출력한다. 풀이 과정 2진수의 길이가 길기 때문에 10진수로 변환하기엔 무리가 있고, 8진수로 다이렉트로 변환해야 한다. 2진수를 오른쪽부터 3자리씩 끊어서 8진수로 바로 변환한다. C #include #include char n[1000005]; int result[1000005]; int result_size = 0; int max(int a, int b) { if (a > b) return a; return b; } int main(void) { scanf("%s", n); int n_size ..

문제 8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오. 입력 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. 출력 첫째 줄에 주어진 수를 2진수로 변환하여 출력한다. 수가 0인 경우를 제외하고는 반드시 1로 시작해야 한다. 풀이 과정 8진수를 10진수로 변환하고, 10진수를 2진수로 변환하기엔 주어지는 수의 길이가 크기 때문에 8진수를 2진수로 바로 변환해야 한다. 8진수를 2진수로 변환하기 위해, 8진수 한 자리당 2진수 세 자리씩 변환하여 출력한다. 맨 앞자리는 무조건 1로 시작해야 함을 유의한다. C 환경에서는 strlen() 을 너무 자주 호출하면, 수의 길이 압박 때문에 시간 초과가 날 수 있음을 주의한다. C #include #include ch..

문제 "두리"라는 나라가 있다. 이 나라에서 사용되는 동전은 1원, 2원, 4원, 8원, 16원, 32원, 64원, 128원, 256원, 512원짜리 이렇게 총 10가지이다. 이 나라의 국민인 아리는 10가지의 동전을 각각 1개씩 총 10개를 가지고 있다. 아리는 샌드위치를 사러 빵집에 가기로 했다. 그런데 빵집에 잔돈이 없어서 샌드위치 가격 S 을 정확하게 지불하지 않으면 샌드위치를 살 수 없다고 한다. 아리가 가지고 있는 동전들을 가지고 계산을 하던 도중 아리의 친구인 쿠기가 마침 빵집에 들어왔다. 쿠기는 10종류의 동전 중에 모든 종류가 아니라 일부 종류의 동전을 각각 1개씩 가지고 있다. 쿠기가 가지고 있는 동전들의 총 금액은 M 원이다. 쿠기는 아리에게 자신이 가진 돈 중에 일부 또는 전체를 흔..

문제 전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다. 처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다. 저항의 값은 다음 표를 이용해서 구한다. black 0 1 brown 1 10 red 2 100 orange 3 1,000 yellow 4 10,000 green 5 100,000 blue 6 1,000,000 violet 7 10,000,000 grey 8 100,000,000 white 9 1,000,000,000 예를 들어, 저항의 색이 yellow, violet, red였다면 저항의 값은 4,700이 된다. 입력 첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 위의 표에 있는 색만 입력으로 주어진다...