C언어 백준 1193번 분수찾기 풀이

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

1193번: 분수찾기

 

문제

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

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번째 분수를 구하는 프로그램을 작성하시오.

 

 

풀이

 

1)배열은 다음과 같이 분류할 수 있다.

1/1					1개
1/2	2/1				2개
3/1	2/2	1/3			3개
1/4	2/3	3/2	4/1		4개
5/1	4/2	3/3	2/4	1/5	5개

 

n =1 일 때 , 첫 행까지는 총 1개

n =2 일 때, 두번째 행까지는 총 1+2개

n =3 일 때, 세번째 행까지는 총 1+2+3개

n =4 일 때, 네번째 행까지는 총 1+2+3+4개

n =5 일 때, 다섯번째 행까지는 총 1+2+3+4+5개

 

 

이를 일반화 하면 n = k 일 때  총 k(k+1)/2 개 

 

이를 활용해 입력 값이 어느 라인에 존재하는지 확인할 수 있다.

예를 들어 입력 값 = 10 이라면 n = 4일 때 총 10개 이므로 4 번째 라인에 존재함을 알 수 있다.

예를 들어 입력 값 = 11 이라면 n = 5일 때 5번째 라인에 존재함을 알 수 있다.

 

                                      ▼

 

(1+ 2 + 3+ 4 + ... + k -1) < 입력 값 <= (1 + 2 + 3 +4 + ... + k ) 일 때, 

입력 값은 k 번째 라인에 있음을 알 수 있다.

 

라인을 찾는 코드

 

#include <stdio.h>

int main() {

	int input;
	scanf("%d", &input);
	int k = 1;
	while (1)
	{		
		if ((k-1)*(k)/2 < input && input <= (k)*(k+1)/2)
		{
			printf("%d\n", k);
			break;
		}
		k++;
	}
	return 0;
}

2)라인에 있는 숫자들의 합은 라인 +1 이다.

1/2

2/1

두번째 라인 의 인수 1/2, 2/1 의 합은 2 +1 = 3

 

3/1

2/2

1/3

세번째 라인의 인수 3/1 , 2/2, 1/3 의 합은 3 + 1 = 4

 

3) 숫자가 홀수번째 라인에 있을 때, 짝수번째 라인에 있을 때

위의 예시에서 보듯

짝수번째 라인에서 인수들은 왼쪽으로 가면서 /를 기준으로 왼쪽은 - 오른쪽은 +

홀수번째 라인에서 인수들은 왼쪽으로 가면서 /를 기준으로 왼쪽은 + 오른쪽은 -

 

2)+3) --> 비교기준(k)(k+1)/2에서 얼마나 떨어져있는지를 통해 인수를 도출해 낼 수 있음.

 

인수 도출 코드

if (k % 2 != 0) // 홀수일 때
	{
		int a = k*(k + 1) / 2;
		printf("%d", (a-input) + 1);
		printf("/");
		printf("%d", k -(a -input));
	
	}
else //짝수 일 때
	{
		int a = k * (k + 1) / 2;
		printf("%d",k-(a-input));
		printf("/");
		printf("%d",(a-input) + 1);
	}

 

(a-input)  는 기준으로부터 얼마나 떨어져 있는지를 확인하기 위한 것이다.

 

정답코드

#include <stdio.h>

int main() {

	int input;
	scanf("%d", &input);
	int k = 1;
	while (1) //라인 찾기
	{		
		if ((k-1)*(k)/2 < input && input <= (k)*(k+1)/2)
		{
			break;
		}
		k++;
	}

	if (k % 2 != 0) // 홀수일 때
	{
		int a = k*(k + 1) / 2;
		printf("%d", a-input + 1);
		printf("/");
		printf("%d", k -(a -input));
	}
	else //짝수 일 때
	{
		int a = k * (k + 1) / 2;
		printf("%d",k-(a-input));
		printf("/");
		printf("%d",a-input + 1);
	}
	return 0;
}

이문제는 프로그래밍 문제라기보단, 수학적 사고력을 요구하는 문제이다.