[백준] 1193 분수찾기

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

표에 있는 분수는 각 표의 좌표로 생각해도 상관 없을 것 같다. 좌표를 이용해서 해당 좌표에 해당하는 답을 찾아야겠다.
문제 설명에 따라 각위치의 순서를 표로 그려보면

1	2	6	7	15	16	28
3	5	8	14	17	27
4	9	13	18	26
10	12	19	25
11	20	24
21	23
22

이렇다.
2칸마다 방향이 비슷하게 가니까 두칸마다 규칙이 있지 않을까? 생각을해서 표를 그려본것이다.
첫 째줄을 2칸씩 띄어서 보면 1 6 15 28 ... 이렇다. 숫자 차이를 써보면 5 9 13 이다. 숫자 차이가 4씩 증가한다. 이 것을 이용해서 문제를 풀 수 있을 것 같다. 고딩때 배웠던 수열이다. 대학교 1, 2학년때도 배웠지만.. 하지만 어떻게 점화식 만들었었는지는 기억이안난다. 대충 만들어보자.
1,1 = 1
1,3 = (1,1) + 5 = 6
1,5 = (1,3) + 9 = 15
1,7 = (1,5) + 13 = 28
...

sum((1,1) ~ (1,2n-1)) = sum((1,1) ~ (1,2n-3)) + (2n-1) * n
(1, 2n-1) = (2n-1) * n
이것을 이쁘게 바꾸면 (1,n) = n * (n+1)/2
이다.
가로로 확인했으니 세로로 확인해보면
마찬가지로 첫째 줄을 두칸씩 띄워서 보면 1,4,11,22로 비슷한 규칙이다.
1,1 = 1
3,1 = (1,1) + 3 = 4
5,1 = (3,1) + 7 = 11
7,1 = (5,1) + 11 = 22
...

sum((3,1) ~ (2n-1,1)) = sum((1,1) ~ (2n-3, 1)) + (2n-1)(n-1)
(2n-1,1) = (1,1) + (2*n-1) * (n-1)

설명하다보니 귀찮아서 여기까지 설명하겠다 궁금하면 댓글 남겨라. 어떻게 점화식을 찾아서
(y,x) = (y(y-1)+(2y+x)(x-1))/2 + 1 이 나왔다. 이것은 홀수에 대해서 계산한것이다. 분류가 수학이어서 수학으로 풀고 있는데 아 주 힘들다.. 그런데 x,y만 바꾸면 짝수에 대해서도 맞다. 왜 맞는지는 확인하기 귀찮으니 그냥 그러려니 하련다.

 

이렇게 검증해보니

대강 맞다.

이제 숫자 x가 주어졌을 때 그게 어느 좌표에 있는지 binary search로 찾아서 문제를 해결해보겠다.

 

package main

import (
	"bufio"
	"fmt"
	"os"
)

func evaluate(y, x int) int {
	if (y+x)%2 == 0 {
		y, x = x, y
	}
	return (y*(y-1)+(2*y+x)*(x-1))/2 + 1
}
func printAnswer(x, ans int) {
	for i := 1; i < ans; i++ {
		if x == evaluate(1+i, ans-i) {
			fmt.Printf("%d/%d", ans-i, 1+i)
			return
		}
	}
}
func main() {
	var x int

	io := bufio.NewReader(os.Stdin)
	fmt.Fscanf(io, "%d", &x)

	var l, r, m, ans, ansV, v int
	l = 1
	r = 4472
	for l <= r {
		m = (r + l) / 2
		v = evaluate(1, m)
		if x <= v {
			ans = m
			ansV = v
			r = m - 1
		} else {
			l = m + 1
		}
	}

	if ansV == x {
		fmt.Printf("%d/1\n", ans)
		return
	}
	m = evaluate(ans, 1)
	if x < m {
		ans = ans - 1
	} else if x == m {
		fmt.Printf("%d/%d", 1, ans)
	}
	printAnswer(x, ans)
}