[백준 7단계] 1193 분수찾기 (군수열)

🥕 [ 백준 1193 ] 분수찾기

문제 링크

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

1193번: 분수찾기

 

🍒 문제 분석

다음과 같이 지그재그로 순번으로 분수가 번호가 매겨져있다고 하자. ( 1/1 이 1번, 1/2가 2번 ... )

X번째 분수를 찾아보자.

 

군수열 문제이다.

1군에 1개, 2군에 2개, 3군에 3개 식으로 진행된다.

 

🥑 코드

X = int(input())
count = 1
roomSum = 0
while True:
    roomSum += count
    if roomSum >= X:
        break
    count += 1
temp = roomSum-X 
if count % 2 == 1:
    print('{}/{}'.format(1+temp,count-temp))     # 홀수, 아래에서 위로
else :
    print('{}/{}'.format(count-temp,1+temp))     # 짝수, 위에서 아래로

 

🍓 내 해결 과정

이 게시물 전에 올라왔던 군수열때의 교훈을 바탕으로 수열 합을 식으로 구하지 않고

수열을 roomSum에 더해가면서 X와 비교했다.

 

roomSum이 X보다 크거나 같게되는 순간의 count가 X가 속한 군의 값이다.

문제에서 홀수일 때는 아래에서 위로 올라가고,

짝수일 때는 위에서 아래로 내려간다는 점을 이용하여 조건식을 나누었다.

가령 다음 사진과 같이 X가 3/3 지점 이라면, temp는 2 이다.

count 는 5가 되므로 분모는 5-2 = 3, 분자는 1+2 = 3 이 되는 것이다.

 

짝수일 때는 RoomSum의 위치가 아래에 있다.

 

🍉 깨달은 점 및 정리

1. roomSum이 X보다 크거나 같게되는 순간의 count가 X가 속한 군의 값이다.

2. 군수열은 코드를 쓰는 흐름이 대충 정해져 있기 때문에 숙지하면 시간이 많이 단축되는 문제이다.