BOJ 1193 : 분수찾기

오늘의 문제~

오늘 입력의 범위도 터무니 없이 큰 수인 걸 보니 확실히 규칙성을 찾아야하는 문제라고 생각했다.

1. 규칙성 찾기

입력 수 (N)	분수	블록의 중심 수 (n)
1	1/1	1
2	1/2	2
3	2/1	2
4	3/1	3
5	2/2	3
6	1/3	3
...	...	...

라는 규칙성을 찾을 수 있었고,
입력받은 수 N으로부터 n을 찾아내고, n을 통해 분수를 찾아내는 흐름으로 생각했다.

1~n까지의 합(시그마 합 공식)을 이용하여
n(n-1)/2 < N <= n(n+1)/2 이라는 부등식을 얻을 수 있다.
=> 입력받은 N이 (n-1까지 합한 수)와 (n까지 합한 수)의 사이일 것이라는 의미

2. 입력받은 N으로부터 중심수 n 구하기

N은

1번째까지 중심수는 1,
3번째까지 중심수는 2,
6번째까지 중심수는 3, ...

인 패턴이 이어지므로
N = n(n+1)/2 도 성립할 수 있기 때문에

근의 공식을 이용하여 n의 값을 구하면

n = (((1+8*N)**0.5)-1)/2

로 구할 수 있다. (근의근의~공식공식~ x는 2a분의 -b~ 플러스~마이너스(+-)~ 루트 b제곱 마이너스 4ac~! 그 노래 말하는 거 맞다)

위와 같이 구한 값은 우리가 구하려는 중심수보다 작거나 같게 나오므로 나온 값을 올림하면 중심 수를 구할 수 있다.

3. 중심수로 분수 구하기

입력 수 (N)	분수	블록의 중심 수 (n)
1	1/1	1
2	1/2	2
3	2/1	2
4	3/1	3
5	2/2	3
6	1/3	3
...	...	...

중심수가 1일때는 1/1, 중심수가 3일때는 3/1, 2/2, 1/3...
중심수가 2일때는 1/2, 2/1, 중심수가 4일때는 1/4, 2/3, 3/2, 4/1 에서 알 수 있듯이

중심수가 짝수/홀수인지에 따라 분수의 패턴도 바뀐다.

짝수의 경우에는 중심수->1 / 1->중심수
홀수의 경우에는 1->중심수 / 중심수->1

의 패턴을 가진다.

입력받은 값이 해당 중심 수에서 (0부터 시작하여)몇번째 해당하는 값인지를 변수 i에 구한다.

i = N-1-n*(n-1)/2

(입력받은 수)에서 (1부터 n-1 번째 수까지 합한 값)을 빼면 몇번째인지 1부터 세는 수가 되지만, 분수를 구하는 곳에서 사용할 때는 어차피 0부터 시작하는 수로 계산하는 것이 편리하므로 i를 구할때 -1을 먼저 뺐다.

아까 말한대로 중심수의 홀짝에 따라 코드를 작성하면 ``` if n%2 == 0{ fmt.Printf("%d/%d\n", i+1, n-i) }else{ fmt.Printf("%d/%d\n", n-i, i+1) } ``` 이렇게 나올 수 있다.

결론적으로 작성한 코드는 다음과 같다.

package main

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

func main(){
	var N, n, i int

	stdin := bufio.NewReader(os.Stdin)
	_, err := fmt.Scan(&N)

	if err != nil{
		fmt.Println(err)
		stdin.ReadString('\n')
	} else{
		n = int(math.Ceil((math.Pow(float64(1+8*N), 0.5) - 1)/float64(2)))
		i = N-1-n*(n-1)/2
		if n%2 == 0{
			fmt.Printf("%d/%d\n", i+1, n-i)
		}else{
			fmt.Printf("%d/%d\n", n-i, i+1)
		}
	}
}

야호 오늘분량 끝