[백준-브론즈1] 1193번 분수찾기 (수학, 파이썬)

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

1193번: 분수찾기

 

<내 코드>

- 무한히 큰 배열에 순서대로 분수가 적혀있고, 지그재그 순서대로 n번째 분수일때, 입력으로 주어진 n번째 분수를

  찾는 문제

- 규칙을 찾는데 오래 고민했다,, 체감상 브론즈보다 어려운 느낌

- 규칙은 분수의 순서가 사선을 기준으로 움직인다.

 

- 따라서, 가장 우선 x번째 분수가 몇번째 라인에 있는지 찾아주었다.

  --> line을 1씩 증가시키고, max_num에 line을 누적해서 더했다.(line = n일때, 그 라인은 n개의 분수를 포함한다)

- 그 후 max_num과 x의 갭을 구한다. 

- 사선 라인이 짝수번째 일때는 순서가 아래로 증가하고, 사선 라인이 홀수번째 일때는 순서가 아래로 감소하기 때문에

  이를 구분해서 분모와 분자를 구해준다.

x = int(input())

line = 0
max_num = 0
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('{}/{}'.format(top,under))

 

 

<내 코드2>

- 위와 비슷한 코드인데 초반에 고생했던 코드,,

- 배열은 '무한히'크고, 이 또한 사선라인을 찾아야하기 때문에 최대 입력일 때 사선라인을 미리 구해서 for문을 통해 

  라인을 찾아주었다.

- 그리고 사선의 제일 위 순서를 start_num에 저장했다, 이때 홀수 일땐 시작 순서가 1 증가하고, 

  짝수일땐 시작 순서가 (step = line*2)만큼씩 증가한다.

- line을 찾은 후 조건에 따라 x번째 분수를 찾아준다.

  -> 라인이 1일땐 1/1밖에 없으므로 1/1을 출력하고

  -> 라인이 짝수이면 사선으로 내려가면서 순서가 증가한다.(이때 내려가면서 분자는 증가, 분모는 감소)

  -> 라인이 홀수이면 사선으로 내려가면서 순서가 감소한다.

target = int(input())

# 라인 찾기
line_sum = 0
start_num = 1
step = 0
for line in range(1,5001):
    line_sum += line
    if target <= line_sum:
        break
    
    if line % 2 !=0: #홀수이면
        start_num+=1
    else:
        step = line*2
        start_num += step

if line ==1:
    print('1/1')    
elif line % 2 == 0: # 짝수일땐 start_num에서 사선으로 내려가면서 숫자 증가
    x, y = 1, line
    for _ in range(line):
        if start_num == target:
            print('{}/{}'.format(x,y))
            break
        x+=1
        y-=1
        start_num+=1
    
elif line %2 != 0: # 홀수일땐 start_num에서 사선으로 내려가면서 숫자 감소
    x, y = 1, line
    for _ in range(line):
        if start_num == target:
            print('{}/{}'.format(x,y))
            break
        x+=1
        y-=1
        start_num-=1