1193 백준 분수 찾기 C/C++

분수찾기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

256 MB

74419

36607

31865

50.903%

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

 

출력

첫째 줄에 분수를 출력한다.

예제 입력 1 복사

1

예제 출력 1 복사

1/1

예제 입력 2 복사

2

예제 출력 2 복사

1/2

예제 입력 3 복사

3

예제 출력 3 복사

2/1

예제 입력 4 복사

4

예제 출력 4 복사

3/1

예제 입력 5 복사

5

예제 출력 5 복사

2/2

예제 입력 6 복사

6

예제 출력 6 복사

1/3

예제 입력 7 복사

7

예제 출력 7 복사

1/4

예제 입력 8 복사

8

예제 출력 8 복사

2/3

예제 입력 9 복사

9

예제 출력 9 복사

3/2

예제 입력 10 복사

14

예제 출력 10 복사

2/4

 

 

 

#include <iostream>
#include <cstring>


using namespace std;
int main(void)
{
	int n;
	cin >> n;
	int index = 0;
	int sum;

	while (1)
	{
		index++;
		sum = index * (index + 1) / 2;
		if (n <= sum)
			break;
	}
	int num = n - (index - 1) * index / 2;

	if (index % 2 == 0)
		cout << num << '/' << index - num + 1;
	else
		cout << index - num + 1<<'/'<< num;
	return 0;
}

 

솔직히 어렵다. 

브론즈는 쉽다고 한 사람은 똑똑한 분들인 것 같다.

유투브에 알고풀이님 코드를 보고 이해했다.

 

풀이를 보면 몇 가지 스텝이 있다.

1) 몇 번째 줄에 들어갈 것인가?

1/1           (1)

1/2 2/1      (2)

1/3 2/2 3/1 (3) 

 

이런식으로 1,2,3증가해간다. 그렇기에 (1) 을 첫째줄이라 하고 (2)를 둘째줄이라 하면, 구하려는 값이 몇 번째 줄에 있는지를 찾아야한다.

 

그 값이 1+2+3+4+.... +n이다. 등차수열의 공식의 의해 n(n+1)/2가 갯수를 구할 수 있다. 

이 값을 sum에 넣고, 입력한 값이 sum보다 크면 반복문을 종료한다.

여기서 나오는 n값이 몇번째 줄인지를 나타내준다.

 

2) 그러면 여기서 인덱스를 구해야하는데, 4번째 줄에 값이 있다고 하면 3번째 줄까지는 값이 6개가 있다. 그럼 3까지의 갯수의 합을 구해서 입력한 값에서 빼주면 된다.

원래 구하던 값이 n(n+1)/2로 값을 구했으니까 인덱스가 하나 적은건 n에 n-1을 대입하여 (n-1)n/2가 되고, 이를 입력한 값에서 빼준다.

 

3) 짝수줄이면 분자가 감소하고 분모는 증가하며, 홀수줄이면 그 반대이다. 짝수와 홀수로 나누어서 생각한다.

홀수줄이면 1,2,3,4 이런식으로 분모가 증가하기에 분모에 num을 쓰고 짝수줄이면 분자가 1,2,3,4 이렇게 올라가기에 분자에 num을 쓴다