[백준] 1193 분수찾기 (수학, 구현, 브론즈1, Python ver.)

링크

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	256 MB	78557	38769	33688	50.984%

문제

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

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

입력

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

출력

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

 

예제 입출력(다들 이해가 안 가는지 예제를 10개나 올려놨다)

예제 입력 1

1

예제 출력 1

1/1

예제 입력 2

2

예제 출력 2

1/2

예제 입력 3

3

예제 출력 3

2/1

예제 입력 4

4

예제 출력 4

3/1

예제 입력 5

5

예제 출력 5

2/2

예제 입력 6

6

예제 출력 6

1/3

예제 입력 7

7

예제 출력 7

1/4

예제 입력 8

8

예제 출력 8

2/3

예제 입력 9

9

예제 출력 9

3/2

예제 입력 10

14

예제 출력 10

 

2/4​

 

 

문제풀이

1/1 -> 1 => 1/1 = before

 

1/2 -> 2 => 1 / (before+1)

2/1 -> 3 => (before+1) / 1

            => before += 1

3/1 -> 4 => (before+1) / 1

2/2 -> 5 => (before+1)-1 / 1+1

1/3 -> 6 => 1 / (before +1)

            => before += 1

1/4 -> 7

2/3 -> 8

3/2 -> 9

4/1 -> 10

 

5/1 -> 11

4/2 -> 13

3/3 -> 13

2/4 ->14 

1/5 -> 15

 

1/6 -> 16

...

 

이런 식으로, 한 대각선씩 내려갈 때마다, 분모 혹은 분자가 1씩 늘어가서, 뒤집어질 때까지 반복한다.

 

나의 오답

- 시간초과 코드

X = int(input())
max = 1 #분자, 분모 최대치
cnt = 0
ans = '/'
check = 1 #0이면 분자가 1부터, 1이면 분모가 1부터

while cnt < X:
    if check == 0:
        for i in range(1, max+1):
            cnt += 1
            if cnt == X:
                print(str(i)+'/'+str(max+1-i))
                break
        check = 1
        max += 1
    elif check == 1:
        for i in range(1, max+1):
            cnt += 1
            if cnt == X:
                print(str(max+1-i)+'/'+str(i))
                break
        check = 0
        max += 1

 

 

정답

- 참고: https://ooyoung.tistory.com/84

X = int(input())

line = 0  # 사선 라인
max_num = 0  # 입력된 숫자(X 변수)의 라인에서 가장 큰 숫자
while X > max_num:
    line += 1  
    max_num += line  

gap = max_num - X 
if line % 2 == 0:  # 사선 라인이 짝수번째 일 때
    top = line - gap  #분자
    under = gap + 1  #분모
else :  # 사선 라인이 홀수번째 일 때
    top = gap + 1  #분자
    under = line - gap  #분모
print(f'{top}/{under}')

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	…	…	…	…	…
…	…	…	…	…	…

예제 입력 10처럼, X = 14가 들어왔다고 생각해보자

 

먼저 입력(X)이 들어오면, 사선 라인이 몇 번째인지 체크하는 line, 입력된 숫자(X)의 라인에서 가장 큰 숫자를 저장하는 max_num변수를 초기화해준다.

 

X > max_num인 동안,

line은 1씩 증가하고, max_num은 line 번째만큼 더해준다.

line이 1이면, max_num은 1

line이 2이면, max_num은 3

line이 3이면, max_num은 6

line이 4이면, max_num은 10

line이 5이면, max_num은 15이다.

 

X < max_num이 되어 반복문을 종료한다.

 

gap = max_num - X으로 정해준다. gap = 15 - 14 = 1이다.

아까 구한 line이 짝수이면, 분자를 line - gap으로, 분모는 gap + 1로 한다.

line이 홀수이면, 분자를 gap + 1으로, 분모는 line - gap으로 한다.

현재 경우는 line이 5이므로 분자는 1 + 1 = 2, 분모는 5 - 1 = 4이다.

 

14가 입력이면, 답은 2/4이다.

 

X = 9인 경우,

X > max_num인 동안,

line은 1씩 증가하고, max_num은 line 번째만큼 더해준다.

line이 1이면, max_num은 1

line이 2이면, max_num은 3

line이 3이면, max_num은 6

line이 4이면, max_num은 10

종료

 

X < max_num이 되어 반복문을 종료한다.

 

gap = max_num - X으로 정해준다. gap = 10 - 9 = 1이다.

아까 구한 line이 짝수이면, 분자를 line - gap으로, 분모는 gap + 1로 한다.

line이 홀수이면, 분자를 gap + 1으로, 분모는 line - gap으로 한다.

현재 경우는 line이 4이므로 분자는 4 - 1 = 3, 분모는 1 +1 = 2이다.

 

9가 입력이면, 답은 3/2이다.

X = 8인 경우,

X > max_num인 동안,

line은 1씩 증가하고, max_num은 line 번째만큼 더해준다.

line이 1이면, max_num은 1

line이 2이면, max_num은 3

line이 3이면, max_num은 6

line이 4이면, max_num은 10

종료

 

X < max_num이 되어 반복문을 종료한다.

 

gap = max_num - X으로 정해준다. gap = 10 - 8 = 2이다.

아까 구한 line이 짝수이면, 분자를 line - gap으로, 분모는 gap + 1로 한다.

line이 홀수이면, 분자를 gap + 1으로, 분모는 line - gap으로 한다.

현재 경우는 line이 4이므로 분자는 4 - 2 = 2, 분모는 2 +1 = 3이다.

 

8가 입력이면, 답은 2/3이다.

 

=> 사선 라인이 짝수번째일 때는 우측 상단에서부터 좌측 하단으로 이동하고,

사선 라인이 홀수번째일 때는 좌측 하단에서부터 우측 상단으로 이동한다.

 

line이 짝수이면, 1/4, 2/3, 3/2, 4/1과 같이

분자가 X에 가까워질수록 커지고, 분모는 X에 가까워질수록 작아진다.

line이 홀수이면, 5/1, 4/2, 3/3, 2/4, 1/5와 같이

분자가 X에 가까워질수록 작아지고, 분모는 X에 가까워질수록 커진다.

 

해당 line에서 제일 큰 수에서 입력받은 수를 빼서 gap이라는 변수를 구한다.

gap변수에 1을 더한 값과, line 변수에서 gap 변수를 뺀 값을 이용해서 분자, 분모를 구한다.

 

line이 홀수일 때, 짝수일 때 분자, 분모 정하는 방식을 다르게해야 해답이 나온다.

블로그에 친히 설명이 있었는데 바보같이 해석하고 있었다...

내일은 DP나 다시 풀어야겠다.