[백준] 1193번: 분수찾기 | C++ 풀이

# 문제

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

 

 

 

---

 

# 풀이

이번에도 지난 번 두 문제와 같이 규칙찾기 문제다.

단계별 풀이에서 제공해주는 문제 순서에 맞춰 풀이하기를 권한다.

 

앞선 두 문제를 풀고 오신 분들이라면 규칙부터 한 번 찾아보자.

 

 

분수는 다음과 같은 순서로 넘버링이 되고 있다.

이때 우리는 대각선별로 숫자를 구분해볼 수 있는데 다음 그림을 확인해보자.

 

 

 

우선 분자, 분모의 합이 같은 대각선으로 그룹을 지어줄 수 있다.

분자와 분모 합이 2인 1/1은 1번 대각선

분자와 분모 합이 3인 2/1, 1/2는 2번 대각선

합이 4인 3/1, 2/2, 1/3은 3번 대각선과 같은 식이다.

 

 

여기서 다시 한 번 진행방향에 따라 대각선을 구분해주었다.

 

노란색으로 표시된 홀수 대각선은 진행방향이 우상향,

파란색으로 표시된 짝수 대각선은 진행방향이 좌하향한다.

 

규칙성을 찾았으니 구현만 하면 된다.

입력받은 숫자가 몇 번 대각선에 위치해있는지를 파악하고, 분자와 분모를 계산해서 출력하면 정답!

바로 정답 소스코드를 확인해보자.

 

 

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);	// 두 표준 입출력 동기화 해제

    int line = 1;
    int x;
    cin >> x;

    // X가 위치한 대각선 찾기
    while(x - line > 0){
        x -= line;
        line++;
    }

    // 대각선 홀수일 때
    if(line % 2) cout << line + 1 - x << '/' << x;
    // 대각선 짝수일 때
    else cout << x << '/' << line + 1 - x;

    return 0;
}

 

우선 대각선 번호를 세어주기 위해 line 변수를 만들고, x로 입력을 받아주었다.

 

 

// X가 위치한 대각선 찾기
while(x - line > 0){
    x -= line;
    line++;
}

그 다음엔 입력된 x번째 분수가 몇 번 대각선에 위치해 있는지를 먼저 찾아주었다.

예를 들어 x 값으로 5가 입력되었을 경우, 

5-1 > 0 이므로 첫번째 루프: x = 4, line = 2

4-2 > 0 이므로 두번째 루프: x = 2, line = 3

2-3 > 0이 성립하지 않으므로 루프 종료  ( x = 2, line = 3 )

위의 과정을 통해 우리는 입력된 5번째 분수가 line 3의 두 번째 순서에 위치해 있다는 것을 알 수 있는 것이다.

 

 

 

// 대각선 홀수일 때
if(line % 2) cout << line + 1 - x << '/' << x;
// 대각선 짝수일 때
else cout << x << '/' << line + 1 - x;

또한 규칙을 찾을 때 확인했듯 진행 방향에 따라 홀수인 대각선, 짝수인 대각선을 나눌 수 있으므로 if-else문으로 구분해주었다. 

 

그림을 다시 한번 확인해보면

 

3번째 대각선에서는 3/1, 2/2, 1/3 순서이므로

홀수에서는 분자에 순서 계산을 마쳐둔 x, 분모에는 line+1 - x 임을 확인할 수 있다.

짝수인 경우에는 진행 방향만 반대이므로 분모 분자를 바꿔주면 된다.

 

규칙은 그래도 나름 빨리 찾은 것 같은데 이를 코드로 구현하는데 조금 머리를 쓴 것 같다.

계속 반복하다보면 이런 사고에 적응하겠지, 라는 마인드로 오늘도 백준!

 

 

 

 

 

---

 

 

1193번: 분수찾기