[백준] 1193번: 분수찾기 [C언어]

📑문제

지그재그 모양의 배열에서 원하는 지점에 값을 찾아라

---

💡 핵심 포인트

무엇을 기반으로 분수를 찾을 것인가?

처음 이 문제를 보았을 때 어떻게 접근할지는 생각이 났지만 무언가 다 애매하고 옳지 않아보이는 접근법 같았다. 배열에 값을 집어넣고 해당 배열에 접근할까? 싶은 생각도 있었으나 그렇게 푼다면 무언가 문제에서 요구하는 방식이 아닌 것 같아서 다른 방법을 생각했다. 메모장에 1부터 시작해서 차근차근 적다보니 무언가 규칙이 보였다.

1/1 → 1/2 → 2/1 → 3/1 → 2/2 → 1/3을 대각선 공간으로 나누어 생각을 하니

1/1

1/2
2/1

3/1
2/2
1/3

1 + 2 + 3 처럼 일정 구간이 나누어지는 느낌을 받았고, 입력 받은 수가 어떤 구간에 위치한지 파악을 하고 문제를 풀면 어떨까 싶은 아이디어로 접근했다.

구간 찾기?

원하는 구간을 찾기 위해서 여러 변수를 이용하여 while문을 이용해서 내가 원하는 구간이 도달할 때까지 반복을 돌렸다.

while (Sum < X)
	{
		Up += 1;
		Sum += Up;
		Count++;
	}

반복문이 종료되게 되면 Count가 분수의 갯수를 나타내게 된다. 예를 들어 입력한 숫자가 4라고 했을 때 Count는 3이되고 현재 지점에서는 분수가 3개(3/1, 2/2, 1/3) 존재한다.

구간을 응용하여 분수 찾기

구간을 찾았으니 분수만 찾으면 되는데 하필 이것이 지그재그 모양이라서 경우를 나누고 접근을 해야했다. 예를 들어 한 번은 1/5로 시작을 했다면 다음 번에는 6/1로 시작을 해야했다. 그래서 Count변수를 이용하여 2로 나누었을 때 나머지를 이용해서 경우를 분리하여 출력해주었다.

❗ 느낀점

풀면서도 계속 이러한 방법으로 문제를 푸는 것이 맞는건가 의문이 들었다.
기본 수학1 의 문제라면 수학적 수식을 이용해서 문제를 풀도록 의도하였을텐데 싶은 생각이 끊임없이 들었다. 일단 나의 방식대로 문제를 풀긴하였으나 다시 한 번 접근법을 생각해야겠다.

---

🧾 전체 코드

#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>

int main()
{
	int X = 0;
	scanf("%d", &X);

	int Sum = 1;
	int Up = 1;
	int Count = 1;

	int a = 1;
	int b = 1;

	while (Sum < X)
	{
		Up += 1;
		Sum += Up;
		Count++;
	}

	//printf("%d %d %d\n", Count, Sum , Up);

	if (Count % 2 == 0)
	{
		a = 1;
		b = Count;

		while (((Sum - Up) + 1) < X)
		{
			a++;
			b--;
			Sum++;
		}
	}
	
	else
	{
		a = Count;
		b = 1;

		while (((Sum - Up) + 1) < X)
		{
			a--;
			b++;
			Sum++;
		}
	}
	printf("%d/%d", a, b);
}