[모의 테스트 풀이] 분수찾기
2021.01.10
안녕하세요! 모의테스트 푸시느라 고생 많으셨습니다. 문제가 맵지 않았나요? 사실, 좀 어려운 문제들이었어요. 알고리즘에 대한 깊은 이해가 필요한 문제들이었습니다. 못푸셨다고 좌절할 필요 없어요(저도 다 못풀어요)! 그럼 풀이를 시작하겠습니다! www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 예시로 주어진 그림을 자세히 보면, 대각으로 규칙이 있습니다. 빨간 대각 선을 기준으로, 분자와 분모의 합은 같습니다. 우리가 찾아낸 규칙을 통해 다음과 같은 규칙을 생각해 볼 수 있을 것 같습니다. 1. 우리가 찾을 X번째의 대략적인 위치를 찾는다. (분모 + 분자를 통해서 2, 3, 3, 4, 4, ..