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

1. 문제 상세

 

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

 

 

 

2. 문제 접근

 

대각선을 따라 지그재그 순서로 분수를 확인하여 해당 순서의 분수를 출력하는 것이 문제이다.

이를 참고해서, 대각선을 보고 규칙을 찾아보자.

 

대각선의 분수들을 보면 i 번째 대각선인 경우 그 대각선에는 i 개의 분수가 있다.

이에 따라 먼저 내가 입력받은 순서가 몇 번째 대각선에 있는지를 확인하자.

이를 확인하기 위해 입력받은 순서 n 에서 i 를 1씩 증가시키며 빼준다.

n 이 i 보다 작거나 같아졌다면 i 번째 대각선에 내가 입력받은 순서가 있다는 것이다.

 

그리고 지그재그 순서이므로 대각선에서 분수들의 순서에도 규칙이 있다.

짝수 i 번 대각선이라고 할 때, 그 대각선 안의 분수는 1/i, 2/i - 1, 3/i - 2, ... i/1 순서이다.

홀수 i 번 대각선인 경우, 대각선 안의 분수는 i/1, i - 1/2, i - 2/3, ... 1/i 순서가 된다.

즉 짝수 i 번 대각선에서는 분자가 1부터 i 까지 증가, 홀수 i 번 대각선에서는 분모가 1부터 i 까지 증가 한다는 것이다.

 

따라서 위에서 n 을 통해 구한 i(대각선 번호)가 홀수인지 짝수인지에 따라 i 보다 작아진 n 이 분모나 분자가 될 것이고,

i 에 1을 더한 값에서 i 보다 작아진 n 을 빼서 나머지 분모나 분자를 구할 수 있다.

 

정리해보면 대각선 i 는 1부터, 입력받은 순서가 n 일때, n 에서 i 를 1씩 증가시키며 빼주고, n 이 i 보다 작거나 같아졌을 때

i 번째 대각선이 짝수번이면 분자가 n, 분모는 그 반대인 (i + 1) - n 값이다.

i 번째 대각선이 홀수번이면 분모가 n, 분자가 그 반대인 (i + 1) - n 값이다.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    int n, i = 1;
    
    cin >> n;
    
    while(n > i) {
        n -= i;
        i++;
    }
    
    if(i % 2 == 0) cout << n << "/" << (i + 1) - n << endl;
    else cout << (i + 1) - n << "/" << n << endl;
}

 

정수 n 과 i 를 선언하고 i 를 1로 초기화한다.

 

cin 으로 정수(순서)를 입력받아 n 에 저장한다.

 

while문으로 n 이 i 보다 큰 경우 반복하도록 한다.

n 의 값에서 i 를 빼고, i 에 1을 더해준다.

 

반복이 끝나면 if 문으로 i 를 2로 나눈 나머지가 0인 경우(즉, 짝수인 경우) n 의 값과 / 문자, (i + 1) - n 값을 출력한다.

위의 경우가 아닐 때(홀수인 경우) (i + 1) - n 값과 / 문자, n 의 값을 출력한다.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

알맞은 규칙을 얼마나 빠르게 찾는지가 문제해결의 관건인 것 같다.