백준 1193번 "분수찾기"

백준 1193번

• 해당 문제는 예제를 활용하여 일련의 규칙을 찾고 그것을 구현한다면 크게 어렵지 않은 문제였다. 

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

1193번: 분수찾기

 

 

처음 제출한 코드

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim();

let num = +input;

let addNum = 2;
let check = 1;

//입력받은 값이 어느부위에 해당하는지 확인
while(check < num){
    check += addNum;
    addNum++;
}

check -= addNum - 2;
let repeat = addNum;

//분수찾기
for(let i = 1; i < repeat; i++){
    let result = "";
    if(check == num){
        console.log(result + i + "/" + (addNum-1));
        break;
    }
    else{
        addNum--;
        check++;
    }
}

 

 

내가 찾은 해당 문제의 규칙은 대각선으로 보았을때 가운데를 기준으로 서로 대칭된다는점이다.

규칙을 찾을때 가장 좋은방법이 일단 해보는것이다.

 

1 - 1/1

 

2-1/2

3-2/1

 

4-3/1

5-2/2

6-1/3

 

7-1/4

8-2/3

9-3/3

10-4/1

 

11-5/1

...

15-5/1

 

 

나열하고 분류해보면 위와 같은 규칙이 보인다.

2와 3이 서로 대칭, 4와 6이 서로 대칭이다.

그리고 이를 한묶음으로 생각했을때 묶음안의 숫자의 개수가

1,2,3,4,5 로 늘어난다.

 

이와 같은 규칙을 발견했을때 생각해낸 방식이

 

1.입력받은 값이 어느 묶음에 해당하는지 알아낸다.

2.해당 묶음의 시작점부터 숫자를 늘려가며 분자는 ++ 분모는 -- 해나간다.

3.만일 입력값과 동일한 숫자가되면 해당 분자와 분모를 출력한다.

 

 

입력받은값이 어느 묶음에 해당하는지 알아내기 위해서 반복문을 적극 활용하였다.

우선 check라는 변수를 선언하여 1부터 찾도록 했고

묶음의 개수가 1씩 늘어가는것을 계산하기 위하여 addNum 이라는 변수를 만들어 반복문 시행시마다 ++을 해주고 check에 더해주었다.

그리고 check변수가 입력값을 넘어가면 반복문을 그만두게 하였다.

 

그리고 위에서 알아낸 범위로 결과 값을 쉽게 구할 수 있었다.

하지만 위 코드가 틀린이유는 문제를 꼼꼼히 읽지 않아서이다...

 

문제의 예제에서는 묶음의 개수가 짝수일때와 홀수일때가 서로 다르다.

즉, 홀수일때는 시작할때 분자가 더크고 짝수일때는 시작할때 분모가 더크다.

그 예시는 아래와 같다.

2- 1/2

3- 3/1

 

7-1/4

11-5/1

 

따라서 해당하는 범위를 다시 한번 확인해줄 필요가 있었다.

 

 

정답으로 제출한 코드

 

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim();

let num = +input;

let addNum = 2;
let check = 1;

//입력받은 값이 어느부위에 해당하는지 확인
while(check < num){
    check += addNum;
    addNum++;
}


check -= addNum - 2;
let repeat = addNum;

//분수찾기
for(let i = 1; i < repeat; i++){
    let result = "";
    if(check == num){
    	//역순점검
        if((repeat-1)%2 != 0){
            console.log(result + (addNum-1) + "/" + i);
        }
        else{
            console.log(result + i + "/" + (addNum-1));
        }
        break;
    }
    else{
        addNum--;
        check++;
    }
}

결과

 

 

위코드에서 틀린부분은 if조건문을 통해 쉽게 구현할 수 있었다.