BOJ1193 분수찾기

문제 바로가기

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

Solved.ac* 난이도

* Solved.ac는 백준 온라인 저지의 문제들에 난이도를 매겨주는 서비스입니다. 자세한 내용은홈페이지를 참고해주세요.

---

본문

---

해설

https://github.com/return0927/CodingWrite-UP/blob/master/BOJ/1193/1193.py

PS를 시작한지 얼마 안되는 생초짜이기 때문에 문제를 푸는 특별한 접근법같은건 없고, 위와 같이 귀납법처럼 경우들을 직접 구해보며 문제를 푸는 편입니다. 문제풀이는 간결함을 위해 경어체를 쓰지 않는 점 양해부탁드립니다.

 

 

배열에 지그재그로 분수가 들어가는데, 지그재그로 따라가다보면 분자+분모의 값이 일정한 구간들이 있다. 각 구간에 번호를 매기면 구간 \(n\)의 길이는 \(n\)이 된다. 따라서 구간 \(n-1\)까지의 길이의 합을 구하면 \(n*(n-1) \over 2\)이고, 각 구간에서 분자와 분모는 1씩 증가/감소를 이어가기 때문에 구하려는 \(X\)가 속한 구간이 몇 번째인지만 구할 수 있다면 구간의 첫머리에서부터 떨어진 거리를 이용해 구하려는 분수를 쉽게 구할 수 있을 것 같다.

 

먼저 구간 \(n\)까지의 원소 개수는 \(n*(n+1) \over 2\)이기 때문에 \(X\)가 속할 것으로 예상되는 구간의 번호를 \(Abstract = A\)라고 하면 다음이 성립한다.

$$Abstract: A = \cfrac{n^2+n}{2}$$

$$\therefore n = -\cfrac{1}{2} + \sqrt{2A+ 0.25} (\because n>=1)$$

 

만약 \(A\)가 자연수라면, 즉 1로 나누어 떨어진다면 구간 \(A = n(=line)\)이고, 자연수가 아니라면 버림을 해서 \(n = int(A)\) 하면 된다.

if abstract == abstract // 1:
    line = int(abstract)
else:
    line = int(abstract) + 1

구간 \(line\)에서 분자와 분모의 합은 \(line + 1\)이기 때문에 구간 \(line - 1\)까지의 원소 개수 합을 구해 \(X\)에서 빼주면 현재 구간에서의 위치를 알 수 있다.

linesum = line + 1
distance = i - (line - 1) * line // 2

위 사진을 다시 보시면 \(distance\)는 \(line\)이 짝수일 때는 분자와, 홀수일 때는 분모와 같다는 사실을 알 수 있고, 이렇게 구한 분자/분모를 \(linesum\)에서 빼주면 나머지 분모/분자를 구할 수 있다.

# Make fountain
up, dw = distance, linesum - distance

if line % 2 == 0:
    dw, up = up, dw

# Print
print('{}/{}'.format(dw, up))

오탈자 혹은 기타 문의는 하단의 댓글 혹은 이메일 personal@return0927.xyz로 부탁드립니다.

감사합니다.