[알고리즘][파이썬] 백준_1193번_분수찾기

[그림1] 화살표를 따라 일정한 규칙으로 반복되는 분수.

제일 왼쪽 상단의 분수(1/1)가 1번이다.

화살표를 따라 분수의 번호가 증가한다(1/2은 2번, 2/1는 3번······.)

번호를 입력 받아 해당하는 분수를 출력해야 한다.

---

1차 시도

# 리스트와 함수를 이용한 풀이(결과 : 시간초과)
lst = []

def odd(n):
    for i in range(1, n+1):
        lst.append('%d/%d'%(n+1-i, i))

def even(n):
    for i in range(1, n+1):
        lst.append('%d/%d'%(i, n+1-i))

ipt = int(input())

for i in range(1, ipt+1):
    if i % 2 == 0:
        even(i)
    else:
        odd(i)

print(lst[ipt-1])

 

리스트와 함수를 이용했다.

값은 정확하게 출력되었으나 제출시 시간초과가 발생했다.

---

2차 시도

# 값 입력을 input 대신 sys.stdin.readline을 이용 시도(결과 : 시간 초과)
import sys

lst = []

def odd(n):
    for i in range(1, n+1):
        lst.append('%d/%d'%(n+1-i, i))

def even(n):
    for i in range(1, n+1):
        lst.append('%d/%d'%(i, n+1-i))

ipt = int(sys.stdin.readline())

for i in range(1, ipt+1):
    if i % 2 == 0:
        even(i)
    else:
        odd(i)

print(lst[ipt-1])

 

2차 시도에서는 값을 입력 받을때 input대신 sys.stdin.readline을 이용했다.

하지만 제출 결과는 달라지지 않았다.

---

3차 시도

# 1, 2차 시도에 사용한 리스트와 함수를 이용한 풀이 방식을 완전히 버렸다(결과: 맞았습니다!).
# 1씩 증가하는 섹터가 존재하고, 섹터는 분자든 분모든 1부터 시작하는 홀수 또는 짝수 개의 숫자를 가지고 있음을 이용하였다.
ipt = int(input())

tmp = ipt
inc = 1

while tmp > inc:
    tmp -= inc
    inc += 1

if inc % 2 == 0:
    mol = tmp
    den = inc-tmp+1
else:
    mol = inc-tmp+1
    den = tmp

print(f'{mol}/{den}') # f-string 사용함

 

성공!

---

해결한 방법

1. 분해, 추상화, 패턴인식을 통한 value 획득

[그림2] 그림1의 '분모/분자'를 추상화 시켜 보았다.

우선 문제에서 패턴을 발견하기 위해 [그림1]에서 '분모/분자'를 분해해 [그림2]와 같이 추상화 시켜 보았다.

이렇게 하니 섹터별로 다음과 같은 패턴을 발견할 수 있게 되었다.

sector	value
sector1	1
sector2	1, 2
sector3	1, 2, 3
sector4	1, 2, 3, 4
sector5	1, 2, 3, 4, 5
…	…

이제 입력값(ipt)과 섹터의 값(value)을 매칭 시켜야하는데

sector	value(ipt)	pattern1	pattern2
sector1	1(1)	0	0
sector2	1(2), 2(3)	1	+1
sector3	1(4), 2(5), 3(6)	3	+2
sector4	1(7), 2(8), 3(9), 4(10)	6	+3
sector5	1(11), 2(12), 3(13), 4(14), 5(15)	10	+4
…	…	…	…

위 표를 보면,

sector별로 입력값(ipt)에 pattern1의 값을 빼줄때 원하는 value를 얻을 수 있다

예) sector5의 입력값 12의 경우 : 12 - 10 = 1 (ipt - pattern1 = value)

 

그리고 pattern2를 보면 pattern1의 값은 sector가 증가함에 따라 기존값에 +1, +2, +3, +4, …와 같이 누적되고 있음을 알 수 있다.

이러한 패턴을 이용해 입력값(ipt)을 임시값(tmp)에 넣고,

임시값이 증가값(inc) 보다 클 경우,

임시값이 증가값 보다 작아질때까지 임시값에 증가값을 빼주었다.

이렇게 하여 입력값에 대응하는 value를 얻을 수 있게 되었다.

ipt = int(input()) # 입력값

tmp = ipt # 임시값
inc = 1 # 증가값(기본값은 1)

while tmp > inc:
    tmp -= inc
    inc += 1

 

2. value를 "분자/분모"로 변환하여 출력

[그림1]을 보면 sector가 홀수냐 짝수냐에 따라 value가 분수의 분자에 또는 분모에 달리 위치하고 있음을 알 수 있다.

※ 스크롤의 불편을 피하기 위해 [그림1]을 다시 가져왔다.

[그림1] 화살표를 따라 일정한 규칙으로 반복되는 분수.

[그림1]을 표로 정리해 보면 다음과 같다.

sector	value	홀/짝	분자(den)	분모(mol)
sector1	1	홀	1	1
sector2	1, 2	짝	1, 2	2, 1
sector3	1, 2, 3	홀	3, 2, 1	1, 2, 3
sector4	1, 2, 3, 4	짝	1, 2, 3, 4	4, 3, 2, 1
sector5	1, 2, 3, 4, 5	홀	5, 4, 3, 2, 1	1, 2, 3, 4, 5
…	…	…	…	…

따라서 sector가 홀수 인지 짝수인지에 따라 해당하는 분자와 분모를 위치 시켜 출력하면 된다.

이때, 증가값(inc)을 이용해 sector의 홀/짝 여부를 판별했다.

반복문(while)을 통해 최종 결정된 inc가 sector 번호를 알려주기 때문이다. 

예) 입력값(ipt)이 14라면, tmp - inc = tmp 식을 반복 계산한다.
14 - 1 = 13
13 - 2 = 11
11 - 3 = 8
8 - 4 = 4
4 - 5 = -1
반복문이 종료될때 tmp는 4, inc는 5가 된다.
tmp는 분자와 분모의 값으로, inc는 sector번호로 각각 사용된다.

if inc % 2 == 0: # 증가값(inc)이 짝수인가?
    mol = tmp
    den = inc-tmp+1
else: # 아니면 홀수인가?
    mol = inc-tmp+1
    den = tmp

print(f'{mol}/{den}') # f-string 사용함