[c++] 1193번 : 분수찾기

문제

 

코드

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;

	int line = 1;

	while (n - line > 0)
	{
		n -= line;
		line++;
	}

	if (line % 2 == 1)
	{
		cout << line + 1 - n << "/" << n << endl;
	}
	else
	{
		cout << n << "/" << line + 1 - n << endl;
	}
	return 0;
}

 

문제 해설

int n;
cin >> n;
int line = 1;

사용자로부터 n을 입력받습니다. 

line은 몇 번째 대각선인지 나타냅니다. 

이렇게 대각선 순서대로 1, 2, 3, 4, 5 로 라인을 계산을 해줄 것입니다. 라인을 구해주는 이유는 라인을 구해야 공통점이 나오기 때문입니다. 

while (n - line > 0)
{
    n -= line;
    line++;
}

while 루프를 통해 n이 몇 번째 위치의 대각선이 있는지 구해줍니다. 각 반복에서 n은 line의 값을 빼고 line을 증가시킵니다. 

 

예를들어 n  = 7이라고 가정을 해봅시다. 그러면 초기에는 n = 7이고 line은 1이 될 것입니다.

1. 첫 번째 루프
n = 7 - 1 = 6
line = 2

2. 두 번째 루프
n = 6 - 2 = 4
line = 3

3. 세 번째 루프
n = 4 - 3 = 1
line = 4

루프 종료 : n = 1 line = 4

이렇게 나오게 됩니다. 이런 식으로 line을 구해주는 것입니다. 이렇게 해줄 수 있는 이유는 line이 1, 2, 3, 4, 5 개가 각 라인에 들어있기 때문에 가능한 것입니다. 여기서 n은 대각선에서 첫 번째 위치에 있음을 확인할 수 있습니다. 

 

if (line % 2 == 1)
{
    cout << line + 1 - n << "/" << n << endl;
}
else
{
    cout << n << "/" << line + 1 - n << endl;
}

여기서 조금의 어려움을 느끼셨을 수 있을 거라 생각이 듭니다. 이는 각 대각선에서 분수가 배치되는 순서를 보면 됩니다. 

 

분수는 다음과 같은 방식으로 대각선 순서로 배치됩니다.

 

첫 번째 대각선: 1/1
두 번째 대각선: 1/2, 2/1
세 번째 대각선: 3/1, 2/2, 1/3
네 번째 대각선: 1/4, 2/3, 3/2, 4/1

대각선의 홀수 / 짝수에 따라 분수가 증가하는 방향이 다른데요.

 

홀수 대각선 : 분자는 감소하고 분모는 증가 (진행방향 : 우상향)

짝수 대각선 : 분자는 증가하고 분모는 감소 (진행방향 : 좌하향)

 

홀수 대각선의 규칙

분자는 감소, 분모는 증가

 

즉 line이 홀수일 때 첫 번째 요소는 line/1이고 마지막 요소는 1/line 입니다. 이를 일반화하면 n번째 위치의 분자는 line+1-n, n번째 위'치의 분모는 n

 

따라서 분수는 line+1 -n / n이 됩니다.