백준 1193번
https://www.acmicpc.net/problem/1193
1. 문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
1/1 | 1/2 | 1/3 | 1/4 | 1/5 | … |
2/1 | 2/2 | 2/3 | 2/4 | … | … |
3/1 | 3/2 | 3/3 | … | … | … |
4/1 | 4/2 | … | … | … | … |
5/1 | … | … | … | … | … |
… | … | … | … | … | … |
이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
2. 내가 작성한 알고리즘
inp=int(input())
n=0
while inp>0:
n-=1
inp+=n
n=n*-1
inp=inp+n
num=n+1
if n%2==0:
print(str(inp)+"/"+str((num-inp)))
else:
print(str(num-inp)+"/"+str((inp)))
3. 이번 알고리즘을 통해 배운 점
순서는 다음과 같다 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3....
이런 식으로 1 12 123 1234.. 과 1 21 321 4321 를 이용하여 수를 배치한다.
첫 번째로는 순서를 찾는다. 값을 누적해서 입력한 값을 뺀다 (0보다 작을때 까지) . 예를 들면 14면 5번째 순서이다.
두 번째로는 반복문이 종료된 이후의 값에 순서 값을 더한다. 이 값은 증가되는 값이다.
세 번째로는 순서값+1 이 바로 분모와 분자를 합친 값이다. 그러므로 증가되는 값에 순서값 +1 을 빼주면 나머지 값을 구할 수 있다. 이 값은 감소되는 값이다.
네 번째로는 순서 값이 홀수 일때는 감소/증가 이고 짝수 일때는 증가/감소 이기때문에 해당하는 조건을 넣어줘서 출 력한다.
'Python > 백준 알고리즘 (파이썬)' 카테고리의 다른 글
브루트 포스 practice 03_ 덩치 (0) | 2021.08.11 |
---|---|
스택 practice 01 _ 균형잡힌 세상 (0) | 2021.08.09 |
기본 수학 practice 04_ ACM 호텔 (0) | 2021.07.21 |
기본 수학 practice 04_ 달팽이는 올라가고 싶다. (0) | 2021.07.20 |
1차원 배열 practice 04_나머지 (0) | 2021.07.16 |