'수학' 태그의 글 목록 (7 Page)

문제:

19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다.

D(T1,T2) =| x1-x2| + |y1-y2|

두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다.

따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다.

원 : 평면 상의 어떤 점에서 거리가 일정한 점들의 집합.

반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 반지름 R이 주어진다. R은 10,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다.

풀이 방법:

수학적 지식을 활용하면 쉽게 풀 수 있는 문제이다. 일반 유클리드 기하학에서의 원의 넓이는 pi*r^2 (r은 반지름)이다. 하지만 비유클리드 기하학, 즉 택시 기하학에서의 원은 우리가 일반적으로 알고 있는 둥근 모양이 아니라 마름모 모양이 나오게 된다.

택시 기하학에서 중심이 원점이고 반지름이 1인 원은 (0,1) (1,0) (-1,0), (0,-1)의 끝 값을 가지고 (+-1/2, +-1/2)인 끝 값 사이의 중간 값을 가져서 이를 모두 이으면 마름모 모양이 나오게 된다. 마름모 모양의 넓이는 지름^2 *(1/2)로 구할 수 있으므로 이 문제에선 2*r^2(r은 반지름) 으로 넓이를 구할 수 있다.

ps)이 문제에서 math 모듈의 pi를 사용해서 문제를 풀었더니 오답을 받아서 직접 pi의 값을 길게 잡아서 계산했더니 맞았다.

1
2
3
n=int(input())
print('%.6f'% round(n*n*3.14159265358979323846,6))
print('%.6f'% (2*n*n))
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1931. 회의실배정 (0)	2019.07.13
[BOJ]1712. 손익분기점 (0)	2019.07.12
[BOJ]1904. 01타일 (0)	2019.07.10
[Programmers]Lv 3. 기지국 설치 (0)	2019.07.09
[Programmers]Lv 3. 섬 연결하기 (0)	2019.07.08

문제:

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궃은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0 타일을 두 개 붙인 한 쌍의 00 타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때, 1만 만들 수 있고, N=2일 때는 00,11 을 만들 수 있다. (01, 10 은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들을 무한히 많은 것으로 가정하자.

입력:

첫 번째 줄에 자연수 N이 주어진다. (N <=1,000,000)

출력:

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

풀이 방법:

전형적인 DP문제 이므로 점화식을 찾으면 쉽게 풀 수 있는 문제이다. 그리고 N= 5까지 숫자들을 나열해보면 규칙을 찾을 수 있다.

N=1일 때 1개, N=2일 때 2개, N=3일 때 3개, N=4일 때 5개, N=5일 때 8개 ....

즉 N=n일 때, N=n-2인 경우 + N=n-1인 경우임을 알 수 있다. 이를 바탕으로 계산을 하면서 각 계산 값에 대해 15746으로 나누면 통과할 수 있다.(맨 마지막 값에 대해서만 나누면 시간초과가 발생할 수 도 있다.)

1
2
3
4
5
6
7
8
9
10
n=int(input())
if n==1:
    print(1)
elif n==2:
    print(2)
else:
    a,b=1,2
    for i in range(3,n+1):
        a,b=(b)%15746,(a+b)%15746
    print(b%15746)
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1712. 손익분기점 (0)	2019.07.12
[BOJ]3053. 택시 기하학 (1)	2019.07.11
[Programmers]Lv 3. 기지국 설치 (0)	2019.07.09
[Programmers]Lv 3. 섬 연결하기 (0)	2019.07.08
[Programmers]Lv 3. 단속카메라 (2)	2019.07.07

문제:

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11]번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다 .(전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

* 초기에 1,2,6,7,8,9번째 아파트에는 전파가 전달되지 않습니다.

* 1,7,9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

* 3개의 아파트보다 더 많은 아파트 옥상에 기지국을 설피할 경우에도 모든 아파트에 전파를 전달할 수 있습니다.

이때, 우리는 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.

변

아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 return하는 solution 함수를 완성해주세요.

문제 풀이:

처음에는 stations에 주어진 기지국으로 인해서 range(N+1) 의 배열이 나누어진다고 생각을 하였고, 그 나눠진 배열들의 길이와 W에 따라 설치해야할 기지국의 수를 알 수 있다고 생각하였다. (어디에 설치하는지는 관심이 없고, 몇 개를 설치하는지가 중요하다.)

일정한 규칙을 따라 하나씩 설치해 나가는 방법도 있긴 이렇게 수학적으로 계산하는 것이 더 편하다고 생각했다. stations의 각 값을 i라고 했을 때 설치해야 하는 기지국의 수는 ((i-w)-(이전의 i+w, 초기값은 1)) / (2*W+1)을 올림한 값이다. 그리고 station의 반복문이 끝나고 아직 남은 아파트가 있을 수 있기 때문에 반복문이 끝난 뒤에도 한번 조건을 탐색해 더 하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
import math
 
def solution(n, stations, w):
    answer=0
    start=0
    for i in stations:
        if i-w>start+1:
            answer+=math.ceil((i-w-start-1)/(2*w+1))
        start=i+w
    if start < n:
        answer+=math.ceil((n-start)/(2*w+1))
    return answer
Colored by Color Scripter
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]3053. 택시 기하학 (1)	2019.07.11
[BOJ]1904. 01타일 (0)	2019.07.10
[Programmers]Lv 3. 섬 연결하기 (0)	2019.07.08
[Programmers]Lv 3. 단속카메라 (2)	2019.07.07
[BOJ]2869. 달팽이는 올라가고 싶다. (0)	2019.07.06

문제:

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 세 정수 A,B,V가 공백으로 구분되어서 주어진다. (1<=B<A<V<=1,000,000,000)

출력:

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

풀이 방법:

문제는 이분 탐색으로 풀라고 했으나 단순한 수학적 지식으로도 쉽게 풀 수 있다. (V-A) /(A-B) 를 ceil 한 값이 달팽이가 V까지 가는 날짜를 의미하며 이 값에다 1을 더해줘서 답을 구할 수 있다.(1일 부터 시작이기 때문)

1
2
3
import math
a,b,v=map(int,input().split())
print(math.ceil((v-a)/(a-b))+1)
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 섬 연결하기 (0)	2019.07.08
[Programmers]Lv 3. 단속카메라 (2)	2019.07.07
[BOJ]1011. Fly me to the Alpha Centauri (0)	2019.07.05
[Programmers]Lv 3. 여행경로 (0)	2019.07.04
[Programmers]Lv 3. 네트워크 (2)	2019.07.03

문제:

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.

그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1, k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0,1,2 광년을 이동할 수 있는 것이다. (여기서 다시 2광년을 이동한다면 다음 시기엔 1,2,3 광년을 이동할 수 있다. )

김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y지점에 도착해서도 공간 이동장치의 안정성을 위하여 y지점에 도착하기 바로 직전의 이동거리를 반드시 1광년으로 하려 한다.

김우현을 위해 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. ( 0<=x <y<2^31)

출력:

각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 공간이동 장치 작동 회수를 출력한다.

문제 풀이:

이 우주선이 움직일 수 있는 형태는 1234....n...4321 과 같은 큰 형태를 가지게 될 것이다. 왜냐하면 거리를 빠르게 이동하려면 큰 값이 필요하고 큰 값으로 접근을 하기 위해서는 1234...처럼 순차적으로 증가해야 하기 때문이다. 그러면 n 즉 어디까지 커져야 할지는 어떻게 정할까?

123...n...321 꼴을 다 더해보면 항상 제곱수가 나오게 된다. 따라서 거리를 제곱수 단위로 구분짓는 것이다.

예를 들어 두 지점 사이의 차이가 21 이라면 이는 16과 25의 차이에 있으므로 4까지 증가해야 한다. (1234321) 하지만 이렇게 이동을 해도 아직 5의 값이 남아있다는 것을 알 수 있다.

이 점은 탐욕적인 방법으로 해결하도록한다. 최대 이동가능한 거리는 4이므로 남은 값을 4부터 채워나가기 시작한다.

1. 5-4 = 1 -> 2. 1-1 =0 따라서 1과 4를 추가해주면 된다. 12343211 과 같이 이동을 해야할 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
import math
for i in range(int(input())):
    n,m=map(int,input().split())
    maxJ=int(math.sqrt(m-n))
    counts=2*(maxJ-1)+1
    remain=(m-n)-(maxJ**2)
    while(remain):
        if remain-maxJ>=0:
            remain-=maxJ
            counts+=1
        else:
            maxJ-=1
    print(counts)
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 단속카메라 (2)	2019.07.07
[BOJ]2869. 달팽이는 올라가고 싶다. (0)	2019.07.06
[Programmers]Lv 3. 여행경로 (0)	2019.07.04
[Programmers]Lv 3. 네트워크 (2)	2019.07.03
[BOJ]11057. 오르막 수 (0)	2019.07.01

문제:

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지않는다.

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표(x1, y1)와 백승환의 좌표(x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다.

출력:

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

풀이 방법:

기하학적 지식을 활용해서 풀어야 하는 문제이다. 입력으로 주어진 값들은 각 원의 중심과 반지름을 나타내는 것이고 류재명이 있을 수 있는 좌표의 수는 두 원의 교점의 갯수가 되는 것이다.

두 개의 원으로 나올 수 있는 교점의 갯수는 다음과 같다.

1. 두 원이 외부에서 접할 때 => 각 원의 중심간의 거리 == 각 반지름의 합 => 1개

2. 두 원이 외부에서 만날 때(접할 때 제외) => 각 원의 중심간의 거리 < 각 반지름의 합 => 2개

3. 두 원이 외부에서 만나지 않을 때 => 각 원의 중심간의 거리 > 각 반지름의 합 => 0개

4. 두 원이 내부에서 만나지 않을 때 => 각 원의 중심간의 거리 < 각 반지름의 차 => 0개

5. 두 원이 내부에서 접할 때 => 각 원의 중심간의 거리 == 각 반지름의 차 => 1개

6. 두 원이 일치할 때 => 중심, 반지름이 모두 일치할 경우 => -1 출력

이 중 4번과 5번의 조건은 2번의 조건과 중첩되는 범위가 있으므로 2번의 세부 조건으로 넣어주도록 한다.

또한 각 원의 중심간의 거리를 구하기 위해서 sqrt를 사용하면 특정 소수점이 짤리는 경우가 발생하기도 한다. 따라서 sqrt를 사용하는 대신의 각 반지름의 합이나 차를 제곱해주는 방법을 사용해서 비교했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def checkIS(x1,y1,r1,x2,y2,r2):
    distance=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)
    if distance==0:
        if r1==r2:
            print(-1)
        else:
            print(0)
    elif distance==(r1+r2)*(r1+r2):
        print(1)
    elif distance<(r1+r2)*(r1+r2):
        if distance==(r1-r2)*(r1-r2):
            print(1)
        elif distance<(r1-r2)*(r1-r2):
            print(0)
        else:
            print(2)
    else:
        print(0)
 
for i in range(int(input())):
    x1,y1,r1,x2,y2,r2=map(int,input().split())
    checkIS(x1,y1,r1,x2,y2,r2)
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1018. 체스판 다시 칠하기 (0)	2019.06.28
[BOJ]1476. 날짜 계산 (0)	2019.06.27
[BOJ]2293. 동전1 (0)	2019.05.20
[BOJ]7568. 덩치 (0)	2019.05.19
[BOJ]2231. 분해합 (0)	2019.05.18

문제:

이제 10 살이 된 헨리(Henry)는 수학에 소질이 있다. 수학선생님인 아메스(Ahmes)는 오늘 헨리에게 분수에 대해 가르쳐줬고, 헨리는 분수를 이리저리 계산해보는 것이 너무 재미있었다. 그러던 중에 헨리는 1 보다 작은 분수를 여러 개의 서로 다른 단위분수의 합으로 표현할 수 있다는 것을 알아내었다. 여기서 단위분수란 분자가 1 인 분수를 말한다. 헨리는 여러 개의 분수에 대해 이를 시도해봤고, 시도해본 분수들은 모두 서로 다른 단위분수의 합으로 표현할 수 있었다. 예를 들어, $\frac{4}{23}$ 은 $\frac{1}{6} + \frac{1}{138}$ 와 같이 두 개의 단위 분수의 합으로 나타낼 수 있다.

헨리는 이런 발견을 선생님인 아메스에게 자랑스럽게 이야기했다. 아메스는 이를 듣고는 크게 기뻐하며 어린 제자를 칭찬했고, 이와 같이 하나의 분수를 서로 다른 단위분수의 합으로 표현한 것을 헨리식 표현법(Henry representation)이라고 이름 지었다. 즉, 분수 $\frac{a}{b}$ 의 헨리식 표현법은 총합이 $\frac{a}{b}$ 와 같게 되는 서로 다른 단위분수의 나열이다. 헨리와 아메스는 헨리식 표현법에 대하여 더욱 연구하였고, 마침내 모든 1 보다 작은 분수는 헨리식 표현법이 가능함을 증명하였다. 또한 헨리식 표현법이 유일하지 않다는 것도 알 수 있었다. 예를 들면, $\frac{5}{7} = \frac{1}{2} + \frac{1}{5} + \frac{1}{70} = \frac{1}{2} + \frac{1}{6} + \frac{1}{21} = \frac{1}{2} + \frac{1}{7} + \frac{1}{14}$ 와 같이 여러 가지 다른 헨리식 표현법이 존재할 수 있다. 단, 정의에 의해, 헨리식 표현법에는 같은 단위분수가 두 개 이상 포함될 수 없으므로 $\frac{2}{3} = \frac{1}{3} + \frac{1}{3}$ 는 헨리식 표현법이 아님을 유념해야 한다.

아메스와 헨리는 또한 주어진 분수의 헨리식 표현법을 구하는 간단한 방법도 고안해냈다. $a < b$ 인 양의 정수 $a$ 와 $b$ 로 이루어진 분수 $\frac{a}{b}$ 가 주어질 때에, 먼저 $\frac{1}{x_{1}} \leq \frac{a}{b}$ 를 만족하는 가장 큰 단위 분수 $\frac{1}{x_{1}}$ 를 계산한다. 그런 다음 $\frac{a}{b}$ 에서 $\frac{1}{x_{1}}$ 를 뺀 나머지에 대하여 위의 과정을 반복한다. 즉, $\frac{1}{x_{2}} \leq \frac{a}{b} - \frac{1}{x_{1}}$ 를 만족하는 가장 큰 단위분수 $\frac{1}{x_{2}}$ 를 계산하고 뺀다. 이러한 과정을 나머지가 남지 않을 때까지 반복한다. 그러면 서로 다른 단위분수들 $\frac{1}{x_{1}}, \frac{1}{x_{2}}, \frac{1}{x_{3}}, \dots$ 을 순서대로 얻게 되며 그들의 합은 정확히 $\frac{a}{b}$ 와 같아진다. 아메스와 헨리는 이 알고리즘이 항상 종료하며 합이 $\frac{a}{b}$ 가 되는 서로 다른 단위분수들, 즉 헨리식 표현법을 출력함을 증명하였다.

아메스와 헨리는 당신에게 그들의 알고리즘을 컴퓨터 프로그램으로 구현해줄 것을 부탁했다. 입력으로 주어지는 1 보다 작은 분수 $\frac{a}{b}$ 를 아메스와 헨리의 알고리즘을 수행하여 헨리식 표현법을 계산할 때에 마지막 단위 분수의 분모를 출력하는 프로그램을 작성하시오. 예를 들어. $\frac{a}{b} = \frac{5}{7}$ 라면, 아메스와 헨리의 알고리즘은 $\frac{5}{7} = \frac{1}{2} + \frac{1}{5} + \frac{1}{70}$ 을 출력하게 되므로 당신의 프로그램은 반드시 70 을 출력해야 한다.

입력:

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T 가 정수로 주어진다. 각 테스트 데이터는 한 줄로 구성되며, 여기에는 입력 분수

\frac{a}{b}

를 의미하는 두 개의 정수

a

와

b

(1 ≤

a

<

b

≤ 10,000) 가 주어진다. 이때,

a

와

b

는 서로소이며, 입력분수

\frac{a}{b}

에 대해 아메스와 헨리의 알고리즘을 실행했을 때에 출력되는 단위 분수가 순서대로

\frac{1}{x_{1}}, \frac{1}{x_{2}}, \frac{1}{x_{3}}, \dots, \frac{1}{x_{m}}

라면,

b x_{1} x_{2} \dots x_{m - 1} < 2^{31}

의 부등식을 만족한다고 가정할 수 있다.

출력:

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 정확히 한 줄을 출력해야 하며 여기에는 정수 하나만을 출력한다. 이 정수는 아메스와 헨리의 알고리즘을 입력 분수 $\frac{a}{b}$ 에 대해 실행했을 때, 출력되는 헨리식 표현법의 마지막 단위분수의 분모와 같아야 한다.

풀이 방법:

가장 큰 1/x를 구하기 위해서는 원래 분수에서 분자를 1로 만들었을 때에 생기는 분모의 값을 올림해주면 된다. (분수의 경우에 분모가 작을수록 크다.)

따라서 (a/b-1/x1-1/x2- .... )의 분자가 1이 될 때까지 while로 반복하도록 한다. 또한 새 분수를 만들고 나서 약분하는 작업이 필요하므로 분수 계산을 도와주는 모듈인 fraction을 사용하도록 한다.

1
2
3
4
5
6
7
8
9
from fractions import Fraction
for i in range(int(input())):
    a,b=map(int,input().split())
    while(a!=1):
        c=b//a+1
        a=a*c-b
        b=b*c
        a,b=map(int,str(Fraction(a,b)).split('/'))
    print(b)
Colored by Color Scripter
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1015. 수열 정렬 (0)	2019.05.16
[BOJ]1547. 공 (0)	2019.05.15
[BOJ]3036. 링 (0)	2019.05.13
[BOJ]2591. 이항 쇼다운 (0)	2019.05.12
[BOJ]2407. 조합 (0)	2019.05.11

문제:

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오,

입력:

첫째 줄에 링의 개수 N이 주어진다. (3<=N<=100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000을 포함하는 사이의 자연수이다.

출력:

출력은 총 N-1 줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

풀이 방법:

모든 링은 첫 번째 링의 크기에 따라서 돌아가는 횟수가 정해지게 된다. 예제의 경우로 보면 첫 번째 링이 12이므로 두 번째 링은 12/3 인 4이고, 세 번째 링은 12/8=3/2, 마지막 링은 12/4 이므로 3이 되게 된다.

python에서는 이러한 분수 약분 및 계산을 해주는 fraction이라는 모듈이 있다. 따라서 첫 번째 링을 기준으로 나머지 링에 대해 분수형태로 만들면 된다. 하지만 정수인 경우에도 분수 형태로 만들어 줘야 하는 작업이 필요하므로, 따로 분류해서 만들어주도록 한다.

1
2
3
4
5
6
7
8
9
from fractions import Fraction
a=int(input())
number=list(map(int,input().split()))
for i in range(1,len(number)):
    result=Fraction(number[0],number[i])
    if int(result)==result:
        print(str(result)+"/"+"1")
    else:
        print(str(result))
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1547. 공 (0)	2019.05.15
[BOJ]10253. 헨리 (0)	2019.05.14
[BOJ]2591. 이항 쇼다운 (0)	2019.05.12
[BOJ]2407. 조합 (0)	2019.05.11
[BOJ]1676. 팩토리얼 0의 개수 (0)	2019.05.10

문제:

n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까?

입력:

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 2^31 -1 을 넘지 않는 두 자연수 n (n>=1) 과 k(0<=k<=n)로 이루어져 있다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력:

각 테스트 케이스에 대해서, 정답을 출력한다. 항상 정답이 2^31보다 작은 경우만 입력으로 주어진다.

풀이 방법:

일반적으로 nCk 를 구하는 문제와 동일하긴 하지만 n과 k의 크기가 많이 크므로 이를 정제하는 작업이 필요하다. 이전 문제에서 nCk를 구할 때 n!/k!*(n-k)!을 통해서 값을 얻는다고 하지만 실제로 사람이 계산할 때는 그렇게 하지 않는다. 10C4가 있다면 10!/4!6!을 통해서 계산을 해야겠지만 사람이라면 약분을 해서 10*9*8*7/4! 으로 구하게 된다. 따라서 이 문제도 약분을 통해서 간략화해야 한다. 또한 nCk=nCn-k와 동일하다는 공식도 존재하므로 k가 일정 값을 넘어가면 이를 통해서 k의 크기를 줄이도록 했다.

1
2
3
4
5
6
7
8
9
10
11
12
while(True):
    m,n=map(int,input().split())
    if m==0 and n==0:
        break
    if m-n<n:
        n=m-n
    answer=1
    for i in range(1,n+1):
        answer*=m
        m-=1
        answer/=i
    print(int(answer))
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]10253. 헨리 (0)	2019.05.14
[BOJ]3036. 링 (0)	2019.05.13
[BOJ]2407. 조합 (0)	2019.05.11
[BOJ]1676. 팩토리얼 0의 개수 (0)	2019.05.10
[BOJ]11051. 이항 계수 2 (0)	2019.05.09

문제:

nCm 을 출력한다.

입력:

n과 m이 주어진다. (5<=n<=100,5<=m<100, m<=n)

출력:

nCm을 출력한다.

풀이 방법:

수학 공식으로 (n k)는 n!/k!(n-k)!과 같다. 따라서 math 모듈에 있는 factorial 함수를 이용해서 계산 하였다.

1
2
3
import math
n,m=map(int,input().split())
print(math.factorial(n)//(math.factorial(m)*math.factorial(n-m)))
cs

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]3036. 링 (0)	2019.05.13
[BOJ]2591. 이항 쇼다운 (0)	2019.05.12
[BOJ]1676. 팩토리얼 0의 개수 (0)	2019.05.10
[BOJ]11051. 이항 계수 2 (0)	2019.05.09
[BOJ]11050. 이항 계수 1 (0)	2019.05.08

수학

문제:

입력:

출력:

풀이 방법:

'Algorithm > Python' 카테고리의 다른 글

문제:

입력:

출력:

풀이 방법:

'Algorithm > Python' 카테고리의 다른 글

문제:

문제 풀이:

'Algorithm > Python' 카테고리의 다른 글

문제:

입력:

출력:

풀이 방법:

'Algorithm > Python' 카테고리의 다른 글

문제:

입력:

출력:

문제 풀이:

'Algorithm > Python' 카테고리의 다른 글

문제:

입력:

출력:

풀이 방법:

'Algorithm > Python' 카테고리의 다른 글

문제:

입력:

출력:

풀이 방법:

'Algorithm > Python' 카테고리의 다른 글

문제:

입력:

출력:

풀이 방법:

'Algorithm > Python' 카테고리의 다른 글

문제:

입력:

출력:

풀이 방법:

'Algorithm > Python' 카테고리의 다른 글

문제:

입력:

출력:

풀이 방법:

'Algorithm > Python' 카테고리의 다른 글

티스토리툴바