1193번
-
[백준 1193번] 분수찾기Algorithm/기타 2019. 12. 27. 20:58
백준알고리즘 1193번 : 분수찾기 어떻게 접근하는 지 알게되고나면 어렵지 않은 문제라고 생각한다. 그러나 언제나 그 접근 방법이 어렵다. 분모와 분자의 합을 S라고 하자, 이 X를 기준으로 1행(혹은 1열)을 보게되면, {2, 3, 4, 5,....} 와 같이 한 개씩 늘어나는 것을 확인할 수 있다. 그리고 행을 기준으로 왼쪽 아래의 대각선으로 한칸씩 내려가면, 하나의 대각선은 모두 동일한 S값을 갖고 있음을 알 수 있다. 그렇다면 우리가 구하고자하는 N번째 수가 1행의 몇 번째 열에 해당하는 대각선에 있는지 알 수 있다면, 적절한 계산을 통해 구할 수 있을 것이다. 각 대각선의 길이는 1, 2, 3...순으로 1씩 증가하는 등차수열이므로, 등차수열의 합 공식 n(n+1)/2 을 이용하여 대각선 길이의..