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

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

1193번: 분수찾기

 

풀이방법

1. 먼저  X(1 ≤ X ≤ 10,000,000) 이라는 것은 일반적인 완전탐색으로는 구할 수 없다.

2. 규칙을 찾아야한다.

3. 먼저 배열을 아래와 같이 보기 편하게 만들었다.

4. 위 배열을 보았을 때 아래와 같이 알아낼 수 있다.

  -홀수 열과 짝수열마다의 규칙이 생긴다.

   -홀수 열 : 분자가 5, 4, 3, 2, 1 로 내림차순이다.

   -짝수 열 : 분자가 1, 2, 3, 4, 5 로 오름 차순이다.

 - 분자 + 분모 = 열 번호 + 1 이다. 

  -즉 1/2 는1+2 = 2번째열 + 1 이다.

5. 위 규칙을 이용해서 N이 주어지면 그에 맞는 분수를 찾아야한다.

7.먼저 열 번호를 구하는 방법이다.

 -1+2+3..를 누적하면서 주어진 N이 어디에 포함되는지 확인한다.

8.열번호를 구했다면 N이 해당 열번호의 그룹에 몇번째인지 알아야한다.

 -지금까지 누적한 수 sum에 주어진 N을 빼면 현재 그룹에서 N이후의 숫자가 몇개인지 알 수 있다.

 -그 숫자에 라인수, 즉 한 그룹에 있는 분수의 갯수를 빼면 몇번째 인지 알 수 있다.

 ->그리고 몇번째 수인지에 따라 분자 혹은 분모 하나가 결정된다.( 1번째이면 1/5 또는 5/1일 수 있다.)

 -> 나머지 분자 혹은 분모를 찾는 방법은 분자 + 분모 = 열 번호 + 1 를 이용한다.

9.마지막으로 홀수번째인지 짝수번째인지를 검사해서 5/1인지 1/5인지를 검사하는 것이다.

 -분자가 홀수번째는 오름차순 짝수번째는 내림차순이므로  이를 통해 구해진 분자 혹은 분모의 숫자를 확정짓는다.

 

내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let N = fs.readFileSync(filePath).toString().trim();

let sum=0;
let line=1;//line을 1+2+3...누적하면서 N이 몇번째 지그재그라인에있는지 확인한다.
while(1){
	sum+=line;
	//누적하는 sum보다 작은 순간이 N의 라인을 확인할 수 있다.
	if(N<=sum){
		let a=line-(sum-N);//만약 line이 5면 sum은 15이다. 거기서 주어진 N이 13이면 15-13=2 하고 line에 2를 빼준다. 
		let b=line+1-a; //a+b는 line수 +1 이므로 b=line+1-a 이다.
		if(line%2==0){ //홀수와 짝수에 따라 a와 b의 값이 분자,분모에 반대로 들어가게 된다.
			console.log(a+"/"+b);
			
		}else{
			console.log(b+"/"+a);
		}
		break;

	}
	line++;

}

 

💢어려웠던 점

1. 규칙을 빨리 찾아내지 못했다.

 -홀수번째와 짝수번째의 오름차순 내림차순의 차이를 파악하지 못했다.

2. 분자혹은 분모를 구하기 위해서는 분자 혹은 분모 하나는 분명히 찾아내야했다. 이를 빨리 생각하지못했다.

 - 분자 + 분모 = 열 번호 + 1 이 공식을 알아냈지만 분자 또는 분모 하나는 알아야 했다. 

 -지금껏 누적한 sum에서 주어진 N을 빼고 거기에 열번호를 빼면 됐었다.