백준 1193_분수찾기.cpp

소스코드

#include <iostream>
using namespace std;
int main(){
    int cnt;
    int denominator = 1;
    int numerator = 1;
    cin >> cnt;
    if(cnt == 1){
    	cout << numerator << '/' << denominator << endl;
    	return 0;
    }
    int group = 1;
    int sum = 0;
    while(cnt > sum){
        group++;
        sum = group*(group+1)/2;
    }
    
    if(group%2 == 0){
        denominator = 1 + (sum-cnt);
        numerator = group - (sum-cnt);
    }else{
        denominator = group - (sum-cnt);
        numerator = 1 + (sum-cnt);
    }
    
    cout << numerator << '/' << denominator << endl;
    return 0;
}

1. 변수
   int cnt : 입력받은 숫자
   int denominator : 분모
   int numerator : 분자
   int group : 군(군수열의 군)
   int sum : 군 내의 총 합

2. 알고리즘
   1) 만약 분모 분자가 둘 다 일인 경우 -> 1/1을 출력한다.
   2) num이 포함되어있는 군(group)을 찾기 위해서 총 항의 개수(sum)가 num을 넘었을 경우까지 반복문을 돌려서 어떤 군에 포함되어 있는지 찾는다.

---

이게 무슨 이야기냐면
cnt : 7이라면 우리는 7번째가 포함된 군을 찾아야 된다. 항의 개수가
1 / 2 / 3 이런식으로 늘어나고 있기 때문에
7이 포함되어 있는 군은 4가 되는 것이다

---

3) 우리가 구한 군(group)는 한 대각선을 말하는 것이다.
여기서 짝수 대각선과 홀수 대각선의 증가 감소 차이가 드러난다. 그래서 두 가지를 나누어서 생각해준다.
짝수 대각선 : 분모 - 1 / 분자 + 1
홀수 대각선 : 분모 + 1 / 분자 - 1

4) 여기서 우리가 위에서 구한 sum값을 돌아봐야 된다. sum은 4군의 가장 마지막 항을 가르치고 있다. 그 이유는 while문에서 해당되는 group의 값을 대입한 값이기 때문이다. 즉 num : 7 group : 4 면 sum은 10이라는 것이다. 그렇기 때문에 sum과 cnt 차이만큼을 짝수/홀수 군에 따라서 더하거나 빼주면 된다.

3. 배운점
   군수열 : 수열 {an}에서 몇 개의 임의의 항을 차례로 묶어 군으로 나눈 수열
   

4. 아쉬운점&느낀점
   정말 많이 고민한 문제이다. 그렇기에 더욱 성취감이 컸던 문제였던 거 같다. 아무리 몰라도 코드를 바로 찾아보지 않고 힌트, 팁 등을 찾아보면서 직접 문제를 해결했던 문제!!
   수학 알고리즘에는 다양한 공식, 수학적 기반이 중요함을 느꼈다. 예전에 군수열 교육과정에서 빠졌다고 공부 안 한거 사아아알짝 후회했다 ㅋㅋㅋ. 이런 내용들을 잘 리뷰해서 코테때 써먹어야 겠다.