2. 백준 1193번 분수찾기 C＋＋

1. 문제

백준 1193번 문제는 주어진 자연수 N에 대해 특정한 규칙에 따라 배열된 분수를 찾아내는 것이 주된 목표이다. 이 문제는 분수를 서로 다른 층으로 나누어 표현하는 방식에 기초한다. 첫 번째 층에는 1/1, 두 번째 층에는 1/2와 2/1, 세 번째 층에는 1/3, 2/2, 3/1의 순서로 배치되는 분수들이 위치한다. 이를 일반화하면 각 층의 번호가 k일 때, k층에는 1/k, 2/(k-,. . , k/1과 같이 배열된다. 이 과정에서 각 층의 분수들은 대각선으로 배열되며, 분수는 각자 위와 아래로 교차하는 패턴을 만든다. 문제의 핵심은 N이 주어졌을 때 이 N이 위치하는 층을 계산하고, 해당 층에서의 분수의 위치를 파악하는 것이다. 그런 의미에서, 층의 번호 k는 N이 언제 누적된 양의 정수들이 끝나는지를 통해 결정된다. 즉, k층까지 포함된 분수의 총 개수를 구하면, 이는 1부터 k까지의 합인 k(k+/2와 같으며, 이 값이 N보다 크거나 같은 최소의 k를 찾는 것이 필요하다. 이를 통해 N의 위치가 어느 층에 속하는지를 판단할 수 있다. 더 나아가, 특정 층 k에서의 N의 위치를 확정짓기 위해서는 N이 해당 층의 최대 개수를 초과하지 않도록 주의해야 한다. k층에는 k개의 분수…