728x90

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

Code

제출 코드(머릿속으로 이해가 끝난 후)

 

제출 코드(직관적으로 보기 좋은 코드)

😢 어떻게 빠르게 해당 집단을 찾아낼 것인지, 해당 집안에서 정답을 어떻게 도출할 것인지가 핵심

😊 2번째 제출코드를 먼저 보면 이해하기 편하다.

다음 표는 지그재그 순서로 진행하는 분수를 더 보기 편하게 정리한 것이다.

1/1          
1/2 2/1        
3/1 2/2 1/3      
1/4 2/3 3/2 4/1    
5/1 4/2 3/3 2/4 1/5  
... ... ... ... ... ...

분모짝수일 때, 오름차순으로(1 2 3 4 5...) 숫자가 진행되는 것을 알 수 있고,
분자짝수일 때, 내림차순으로(5 4 3 2 ...) 숫자가 진행되는 것을 알 수 있다. 홀수는 그 반대다.

패턴을 파악했으니, 어떻게 답을 찾아낼 지 생각해보자.

먼저, 최대로 입력받을 수 있는 수의 크기는 10,000,000이므로 배열이나 테이블로 만드는 건 시간 초과가 날 것이다.
따라서, 찾고자하는 X번을 포함하고 있는 그룹을 찾고, 그 그룹 안에서 X번째 분모/분자 값을 찾아내야 한다.

1/1부터 시작한다고 생각할 때, 해당 그룹의 분수 개수는 1부터 1씩 증가한다.
그룹 개수가 증가할 때마다 입력 받은 X에서 그룹을 빼주면 해당 그룹에 도달했을 때, X는 0 또는 음수가 된다.
위 과정을 while문에서 진행해주면 된다.

여기서 중요한 것은 groupCounter가 곧 해당 그룹의 분수 개수라는 것이다. 이 것을 기억하고 다음 단계로 넘어가보자.

이제 if (group % 2 === 0)을 이용해서 짝수일때, 분모 출력groupCounter + X 로 해주면
해당 그룹의 끝 기준으로 자신의 순번을 찾는다.(12345 처럼 오름차순 기준이기 때문)
그리고 분자1 + (-X) 를 해주면 역시 그룹의 끝 기준으로 자신의 순번을 찾는다.( 54321처럼 내림차순이기 때문)

예를 들어 11번째 분수를 찾아보자.

while(X > 0){} 코드를 통해 groupCounter는 5, X는 -4라는 것을 알아낼 수 있다.
그룹은 5번째이므로 홀수이기 때문에, 분모는 내림차순, 분자는 오름차순이다.
분모 그룹은 54321
분자 그룹은 12345
이며 분모는 1+ -(-4) = 5이므로, 5번째 그룹의 1번째 수이며,
분자는 5 + (-4) = 1이므로, 역시 5번째 그룹의 1번째 수다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

// Find Fraction
 
// 1st Solution
 
// For submit
 
// const fs = require('fs');
// const X = Number(fs.readFileSync('/dev/stdin').toString().trim());
 
// For local test
let X = 14;
let counter = 0;
 
while (X > 0) {
counter++;
X = X - counter;
}
 
if (counter % 2 === 0) {
console.log(`${counter + X}/${1 + -X}`);
} else {
console.log(`${1 + -X}/${counter + X}`);
}
 
// 2nd Solution
 
// For submit
 
// const fs = require('fs');
// let X = Number(fs.readFileSync('/dev/stdin').toString().trim());
 
// For local test
// let X = 11;
// let groupCounter = 0;
// let ascendingNumArr = [];
// let descendingNumArr = [];
 
// while (X > 0) {
// groupCounter++;
// X = X - groupCounter;
// }
 
// for (let i = 0; i < groupCounter; i++) {
// ascendingNumArr.push(i + 1);
// descendingNumArr.push(groupCounter - i);
// }
 
// if (groupCounter % 2 === 0) {
// console.log(
// `${ascendingNumArr[groupCounter - 1 + X]}/${
// descendingNumArr[groupCounter - 1 + X]
// }`
// );
// } else {
// console.log(
// `${descendingNumArr[groupCounter - 1 + X]}/${
// ascendingNumArr[groupCounter - 1 + X]
// }
// `
// );
// }

+ Recent posts