[문제풀이 후기] 백준 #1193 - 분수찾기

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

 

규칙

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

 

이 배열을 / 형태의 대각선으로 분리시킨 뒤 접근 방향대로 배치시킨다면 다음과 같은 형태의 그룹이 생성된다.

1번째 배열 - [ 1/1 ]
2번째 배열 - [ 1/2, 2/1 ]
3번째 배열 - [ 3/1, 2/2, 1/3 ]
4번째 배열 - [ 4/1, 3/2, 2/3, 1/4 ]
5번째 배열 - [ 5/1, 4/2, 3/3, 2/4, 1/5 ]
...

 

여기서 찾을 수 있는 규칙은 총 2가지다.

규칙1)
: N 번째 배열의 요소(=분수) 개수 = N 개

규칙2)
: N 번째 배열의 i 번째 분수 ( 1 ≤ i ≤ N )

2-1) N 이 짝수인 경우
: 분자 = N - i + 1
: 분모 = i

2-2) N이 홀수인 경우
: 분자 = i
: 분모 = N - i + 1

결론
: 입력값이 N 번째 배열의 i 번째 분수인지 찾으면 됨

---

기본 상위 코드

import { readFileSync } from "fs";

const input = readFileSync(0).toString().trim();

// arrayNum: 배열 번호, top: 분자, bottom: 분모
let [arrayNum, top, bottom] = [1, 1, 1];

 

첫 번째 시도 (결과 : 성공)

 

접근 방식

1. targetValue 선언 (기본값 : 0)
2. targetValue 가 입력값보다 커지기 직전까지
  - targetValue = targetValue + arrayNum
  - arrayNum++
3. i 번째 위치는 입력값 - targetValue
4. 이후 arrayNum의 짝수 여부에 따라 분자, 분모 계산

 

const value = Number(input);

let targetValue = 0;

// targetValue가 value보다 커지기 직전까지 반복
while (value > targetValue + arrayNum) {
  targetValue += arrayNum;
  arrayNum++;
}

// 순서 i 도출
const position = value - targetValue;

// arrayNum 짝수 여부
const arrayNumEven = arrayNum % 2 === 0;

top = arrayNumEven ? position : arrayNum - position + 1;
bottom = arrayNumEven ? arrayNum - position + 1 : position;

console.log(`${top}/${bottom}`);

---

두 번째 시도 (결과 : 성공)

 

접근 방식

: 입력값 자체를 사용

1. arrayNum이 입력값보다 커지기 직전까지
  - 입력값 = 입력값 - arrayNum
  - arrayNum++
2. 이후 과정은 첫번째와 동일

 

let value = Number(input);

// arrayNum이 value 보다 커지기 직전까지 반복
while (value > arrayNum) {
  value -= arrayNum;
  arrayNum++;
}

// arrayNum 짝수 여부
const arrayNumEven = arrayNum % 2 === 0;

// position = value
top = arrayNumEven ? value : arrayNum - value + 1;
bottom = arrayNumEven ? arrayNum - value + 1 : value;

console.log(`${top}/${bottom}`);

 

 

후기

규칙 찾기 어렵다..