[백준]_1193 : 분수 찾기(파이썬 and C언어)

 

1193번: 분수찾기

 

분수 표에서 지그재그로 내려오면서 몇 번째 순서에 어떤 분수를 출력할지 고민해야 되는 패턴에 미쳐버린 문제이다.

계단식으로 내려오는 구조

---

규칙 사냥

규칙은 단순 계산의 연속이기 때문에 인간보다 제대로 된 수식만 알려준다면 컴퓨터가 잘 해결해 줄 것이다. 먼저 위의 표를 보면서 규칙을 생각해 보자. 뭔가 시점(빨간 화살표)이 대각선으로 움직이는 것에서 규칙을 찾아내기에는 살짝 불편한 것 같다. 따라서 아래와 같이 표를 변형시켜 주겠다.

1 / 1 (1)
1 / 2 (2)	2 / 1 (3)
3 / 1 (4)	2 / 2 (5)	1 / 3 (6)
1 / 4 (7)	2 / 3 (8)	3 / 2 (9)	4 / 1 (10)

 분수 옆에 있는 (숫자)들은 몇 번째의 분수인지를 가리킨다. 또한 이런 변형된 표로 보니까 규칙이 2개가 보임을 알 수 있다.

1. 각 줄에서 분자와 분모의 합은 항상 일정하다 2(1+1), 3(1+2, 2+1), 4(3+1, 2+2, 1+3)...
2. 각 줄의 원소의 개수는 1씩 증가한다
3. n번째 줄에 대응되는 분자와 분모의 합 m은 n+1=m을 만족한다
4. n번째 줄의 첫 번째 원소의 분자는 n이 짝수일시 1이고 홀수일시 n이다  

---

전략

문제상 x번째 분수가 무엇인지 찾는 것이기 때문에 x번째 분수가 '몇 번째 줄에', '줄의 번호가 짝수인지 홀수인지' 정도만 알아내도 충분할 것으로 보인다. 왜냐하면 관련 공식은 위에서 모두 도출했기 때문이다.

 

---

시도 1 (Python)

x=int(input())
line=1
start, end=1, 3
add=2
while 1:
    if start<x<=end:
        line=add
        start+=1
        break
    elif x==1:
        break
    else:
        add+=1
        start=end
        end+=add
if line%2==0:
    ja=1
    mo=line
    while 1:
        if start==x:
            print(f"{ja}/{mo}")
            break
        else:
            start+=1
            ja+=1
            mo = line + 1 - ja
else:
    mo = 1
    ja = line
    while 1:
        if start == x:
            print(f"{ja}/{mo}")
            break
        else:
            start += 1
            mo += 1
            ja = line + 1 - mo

<평가>

시간대비(44 ms) 코드 길이(621 B)가 너무 길고 쓸데없는 변수들을 너무 많이 만들어주었다. 더 간결한 코드로 만들기 위해 코드를 2개의 큰 부분으로 쪼개서 다시 짜보자.

---

몇 번째 줄? 분자 분모의 합?

x값에 해당하는 줄을 찾으면 자동으로 분자 분모의 합이 결정된다. 어떻게 구할까? 비밀은 해당 줄의 마지막 번호에 있다. 1, 3, 6, 10... 은 전부 1 ~ n(=1, 2, 3, 4...)까지의 합이다. 따라서 lamda fuction으로 수열의 합을 구하는 함수(last)를 만들어주면 last(n-1)+1 <= x <=last(n)을 만족시키는 x를 찾으면 자동으로 n은 x가 존재하는 줄에 해당되고 분자 분모의 합 또한 n으로 결정된다.

import sys
input=sys.stdin.readline
x=int(input())
n=1
last=lambda a:int(a*(a+1)/2)
while 1:
    if last(n-1)+1<=x<=last(n):
        break
    n+=1

출력

이제 분자 분모의 합도 구했으니까 최종 코드는 다음과 같다관계식 찾으려고 시간 오지게 쓴 건 비밀.

import sys
input=sys.stdin.readline
x=int(input())
n=1
last=lambda a:int(a*(a+1)/2)
while 1:
    if last(n-1)+1<=x<=last(n):
        break
    n+=1
if (n)%2==0:
    print(f"{x-last(n-1)}/{n+1-x+last(n-1)}")
else:
    print(f"{n+1-x+last(n-1)}/{x-last(n-1)}")

 

---

추가 정리

분명 람다 함수를 처음 배웠을 때 함수를 간단하게 만들 수 있음에 감탄하고 내가 유용하게 잘 쓸 것이라고 생각했다. 하지만 정작 이 문제를 검토하면서 최초로 사용해 보았다. 생각해 보면 사용하지 않았던 그 이유가 있다. 람다 함수는 오직 사칙연산 밖에 가능하지 않기 때문에 다양한 연산(if, while, for 등이 포함된 연산)을 수행하기 위해서는 적합하지 않다. 또한 자주 나오는 연산구조가 아닌 이상 굳이 만들 필요조차 없음을 알 수 있다.

---

시도 2(C 언어)

다행히도 저번에 포스팅한 백준 1010번 문제처럼 매우 큰 숫자의 크기를 저장하고 난 뒤 계산을 수행할 일이 없다. 따라서 적절히 python코드를 c로 바꾸어주면 될듯하다. 

#include<stdio.h>
int main()
{
	int x;
	scanf("%d", &x);
	int n = 1;
	while (1)
	{
		if ((n - 1) * n / 2 <= x && x <= n * (n + 1) / 2)
			break;		
		n++;
	}
	if (n % 2 == 0)
		printf("%d/%d", x - (n - 1) * n / 2, n + 1 - x + (n - 1) * n / 2);
	else
		printf("%d/%d", n + 1 - x + (n - 1) * n / 2, x - (n - 1) * n / 2);
	return 0;
}