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

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

1193번: 분수찾기

못 풀어서 풀이를 본 문제다.

어떻게든 규칙을 찾으려 해봤지만 나에게는 보이지 않았다.

분자와 분모의 증감도 뒤죽박죽이었다.

힌트를 얻고자 풀이를 구글링 하였는데 가장 좋았던 포스팅은

https://abcdefgh123123.tistory.com/186 이 분의 포스팅이었다. 쓸데없는 내용없이 간결하게 풀이하셨다.

 

복습 겸 되짚어보자.

대각선의 방향이 바뀌는 것을 기준으로 위 표와 같이 정렬할 수 있었다.

맨 우측 열에 쓰인 숫자는 요소의 개수인데

대각선마다 요소의 개수가 1씩 늘어나는 것을 알 수 있다.

여기서 중요한 규칙을 하나 발견해야하는데

요소의 개수가

2번째 대각선일 때 1+2개

3번째 대각선일 때 1+2+3개

4번째 대각선일 때 1+2+3+4개

고등수학에서 많이 본 첫째 항이 1이고 공차가 1인 등차수열의 합 공식

n(n+1)/2가 떠올랐어야했다.

알아서 뭐하는데?문제에서 입력한 값이 위 표 중 어느 행에 속한 줄 알 수 있다.ex) input : 5 output : 3행

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
    int n, x;
    scanf("%d", &n);
    int k = 1;
    while (1) {
        if (k * (k - 1) / 2 < n && n <= k * (k + 1) / 2) break;
        k++;
    }

위 코드와 같이 나타낼 수 있다.

조건문의 이해는 위에 기술한 내용을 기반으로 충분히 이해할 수 있다.

 

그렇게 어디에 위치해있는 지 특정지을 수 있지만 아직 원하는 출력값을 얻지 못했다.

여기서 두 개의 규칙이 더 발견되는데

결론부터 말하자면,

각 행에 속해있는 요소의 분자와 분모의 합은 행 + 1이다. ex)2행 1/2 2/1은 합이 3(2+1)으로 같다.

홀수 행은 분자가 1씩 줄어들고 분모가 1씩 증가하는 반면,짝수 행은 분자가 1씩 증가하고 분모가 1씩 감소한다.

 

이 규칙들을 종합하면 등차수열의 합으로 몇 번째 행의 요소인지 특정할 수 있고

그 행이 홀수냐 짝수냐에 따라 분자와 분모의 값을 적절히 조작하여 내가 원하는 값을 출력 할 수 있다.

행의 맨 왼쪽 요소부터 조작하는 것 보다 행의 값이 들어있는 맨 오른쪽 요소부터 조작하는 것이 간편하다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

내 코드인데 홀수일 때와 짝수일 때 구분하여 어떻게 출력할 것인지에 대해 코드를 작성한 부분이 가독성이 떨어진다.

#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;
}

위 링크의 코드인데 변수를 하나 더 설정하더라도 가독성 좋게 코드를 작성하는 것이 중요하다고 다시 한 번 느꼈다.

 

 

input에 대하여 output에 바로 갈 수도 있지만

위와 같이 어디에 속해있는 지를 먼저 특정지은 다음 output에 도달할 수도 있었다.