[BOJ] 백준 1193 분수찾기 (Swift)

문제

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

1193번: 분수찾기

풀이

먼저 지그재그 순서가 어떻게 되는지 확인을 해봐야 합니다.

보라색으로 색칠한 부분은 아래에서 위 순서로, 주황색으로 색칠한 부분은 위에서 아래의 순서로 진행이 됩니다.
보라색으로 색칠한 부분은 홀수번째 대각선이 되겠네요!
대각선의 크기는 1, 2, 3, 4 ... 순으로 늘어나고 있습니다.

X번째가 주어졌다면 X보다 크거나 같아질 때 까지 대각선의 크기를 더해줘서 몇번째 대각선에 위치했는지 찾을 수 있습니다.

예를들어 X가 7이라면..?
7 <= 1 + 2 + 3 + 4
1부터 4까지 더해줬을 때, 7보다 커지게 되네요!
즉, 4번째 대각선에 위치해 있다는 것을 알 수 있습니다.

이제 4번째 대각선이기 때문에 짝수 라인이고, 주황색으로 색칠한 부분이 되겠군요!
위에서 아래의 순서로 진행이 될 것이고, 분모는 1부터 증가하고 분자는 n부터(4번째 대각선이기 때문에 4) 감소되는 형태일 것입니다.

1부터 3까지 더해줬을 때의 값은 6이고, 1부터 4까지 더해줬을 때의 값이 10입니다.

4번째 대각선은 7 ~ 10번째 수들을 갖고 있어요.

이제 10에서 X를 빼주어서 이 값을 가지고 분수를 만들어 주도록 하겠습니다.

7이라고 가정한다면 10 - 7로 3이네요.

이제 분자의 값을 4(4 번째 대각선) - 3(10 - X)로 설정해주시고, 분모의 값은 (10 - 7) + 1로 설정해주시면 됩니다!
그렇다면 7번째 분수는 1/4, 8번째는 2/3 .. 이런식으로 구할 수 있습니다.

만약 홀수번째 대각선이라면 홀수번쨰는 아래에서 위 순서이기 때문에 짝수번째 대각선에서 분수를 구한 방식과 반대로 구해주시면 됩니다.

소스코드

후기

규칙을 찾아낸다면 쉽게 풀 수 있는 문제이다.
그런데 규칙을 찾는게 조금 까다로웠다.. 지그재그 순서을 이해하는게 어려웠던 문제..