[BOJ/C++] 1193번, 분수 찾기

문제 원본: https://www.acmicpc.net/problem/1193

1193번: 분수찾기

---

[실패]

단계별로 풀어보기를 하던 중 실버 문제가 나와 당황했다. 그래도 일반 수학이라 가벼운 마음으로 참여했다. 이전의 단계별 문제에서는 패턴이 수열의 형태로 나타나서 이번 문제도, 분자와 분모 따로 놓고 수열의 규칙성을 찾아보려 노력했다.

분자: 1, 1, 2, 3, 2, 1, 1, 2, 3, 4, 5, 4, 3, 2, 1,,

분모: 1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1,,,

무언가 규칙은 보인다. 공통점은 최댓값까지 오름차순으로 출력하고 다시 내림차순으로 출력하는, 마치 그래프로 나타내면 산을 만드는 것이다. 그런데 그것이 분자는 최댓값이 1부터 홀수값으로 반복되고, 분모는 2부터 짝수값이 반복된다. 그래서 이런 규칙성으로 문제를 풀어나가려고 머리를 싸매보았는데, 결국 X번째에 분자와 분모가 어떤 수를 갖는지, 그리고 설사 수열을 배열로 나타낸다 해도 배열의 최대 길이를 섣불리 정해두고 문제를 풀 수도 없었기에, 이 방식으로 접근하는 것은 잘못된 것임을 인지했다.

---

잘못된 접근임을 깨닫고 

이 배열의 진행방향이 대각선 방향이므로 문제에서 제시하는 순서대로 한 번 눈알을 굴려봤다(문제에서 단서를 잘 파악하는 것이 중요한 것이라고 생각해서!). 그러더니 어느정도의 규칙이 보이는 것 같았다. i 번째 대각선에서 짝수번째 대각선은 오른쪽으로 갈 수록 분자가 1부터 i까지 감소하고, 분모는 정확히 그 반대로 이동한다. 이 점을 이용하면 될 것 같다는 생각이 들었다.

그래서 입력받은 수 X에서 우리가 구하려는 그 분수가 우선 몇번째 대각선에 있는지 파악하기 위해 i를 1씩 더해가며 X에서 빼 나갔다. 만약 X가 i보다 작아지고 X에 남은 수는 i번째 대각선에서 왼쪽으로부터 X번째 수를 나타낼 것이다. 이때 i가 홀수인지 짝수인지 잘 판단해서 문제를 풀어주었다.

---

//분수 찾기

#include <iostream>
using namespace std;

int main(){

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int X;

    cin >> X;

    int i = 1;
    while(X > i){
        X -= i;
        i++;
    }

    if(i % 2 == 0) cout << X << '/' << i - X + 1 << '\n';
    else cout << i - X + 1 << '/' << X << '\n';

    return 0;
}

문제에서 알려주는대로 단순하게 접근한다면 금방 풀 수 있을 것이다!

 

 

곧 써보고 싶은 글:

- 운영체제에 대하여(Linux 그리고 Windows)

- 입출력 스트림 동기화 해제의 효과(cin.tie(), ios_base::sync_with_stdio()에 대하여)