You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

최대 1 분 소요

1. 문제Permalink

[Bronze I] 분수찾기 - 1193Permalink

문제 링크

성능 요약Permalink

메모리: 30864 KB, 시간: 72 ms

분류Permalink

구현(implementation), 수학(math)

문제 설명Permalink

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

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번째 분수를 구하는 프로그램을 작성하시오.

입력Permalink

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력Permalink

첫째 줄에 분수를 출력한다.

출처: 백준, https://https://www.acmicpc.net/

2. 해결방법 시간복잡도Permalink

  1. 단순 코딩 O(N)

3. 문제 해결 및 코드Permalink

N = int(input())
num = 1
while N > num:
N -= num
num += 1
if num % 2 == 0:
a = N
b = num - N + 1
else:
a = num - N + 1
b = N
print(f'{a}/{b}')
view raw 1193.py hosted with ❤ by GitHub

  • 주석을 참고하면서 이해를 돕습니다.Permalink

4. 알고리즘 및 해설Permalink

  1. while문을 통해 해당 수에서 계속해서 돌아간 수만큼 빼준다.
    • num값을 1부터 시작해서 계속해주고, 이때 N이 num이 되는 순간 멈추게 된다.
  2. 반복문이 끝난 이후 해당 돌아간 횟수가 짝수일 경우
    • N값과 돌아간 횟수에서 N값을 빼고 1을 더한 값을 출력한다.
  3. 반복문이 끝난 이후 해당 돌아간 횟수가 홀수일 경우
    • 돌아간 횟수에서 N값을 빼고 1을 더한 값과 N값을 출력한다.

참고