분수찾기 백준 1193번 c++

문제 링크 

 

 

 

"맞았습니다" 코드 링크

#include <bits/stdc++.h>
using namespace std;

int n, num, i, mo, ja;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;

  while(num < n){ // i: 1, 2, 3, 4, ...
    i++;
    num += i;
  }
  // while문 종료 직후, num은 n보다 같거나 큰 수가 되어 있다.
  int diff = num - n; // 라인 시작점부터 이동할 숫자

  if(i % 2){  // 홀수 라인 - 밑에서 대각선으로 위로 숫자 변화
    ja = 1 + diff;
    mo= i - diff; 
  }
  else { // 짝수 라인 - 위에서 왼쪽 대각선으로 아래로 숫자 변화
    ja = i - diff; 
    mo = 1 + diff;
  }

  cout << ja << '/' << mo;
  return 0;
}

 

리뷰 

 

1. 대각선 라인을 기준으로 생각한다.  순서를 떠나서, 그림 그대로 바라보면 아래와 같다. 

 

[홀]  1번째 라인 : 1/1

[짝]  2번째 라인 : 2/1 , 1/2 

[홀]  3번째 라인 : 3/1, 2/2, 1/3

[짝]  4번째 라인 : 4/1, 3/2, 2/3, 1/4

 

2. 짝수 라인과 홀수라인에서 분자와 분모가 어떻게 변하는지 보면 규칙을 발견할 수 있다. 

 

짝수 2번째 라인 :  2 / 1  ,  1 / 2 

=> 분자 : 시작 2, 종료 1  (분자는 감소)

=> 분모 : 시작 1, 종료 2  (분모는 증가)

홀수 3번째 라인 :  3 / 1  ,  2 / 2,  1 / 3 

=> 분자 : 시작 3, 종료 1

=> 분모 : 시작 1, 종료 3 

 

 

3. 주어진 숫자 n이 홀수라인에 속하는지, 짝수 라인에 속하는지 확인해야 한다. 

  cin >> n; // n 번째 칸이 홀수 라인인지 짝수 라인인지 확인하기.

  while(num < n){ // i: 1, 2, 3, 4, ...
    i++;
    num += i;
  }

1번째는 1개 분수가 있다.

2번째 라인에는 2개 분수가 있다. num에 1, 2, 3, 4 .. 씩 더해주며 몇 번째 라인에 속한건지 반복문 돌린다.  

반복문 끝나면, 숫자 n은 i 번째 라인에 속한다. 

while문 종료 직후, num은 n보다 같거나 큰 수가 되어 있다. 반복문 마지막에 무조건 i를 더하고 종료하기 때문이다. 

 

4. offset 확인한다.

diff 변수 :  라인 내부에서 몇 번째 숫자인지를 나타낸다. 

 

i 가 짝수인 경우.

짝수 라인에서 분자는  i에서 시작한다. --> i - diff 

짝수 라인에서 분모는 1에서 시작한다. --> 1 + diff 

 

짝수 2번째 라인 :  2 / 1  ,  1 / 2 

=> 분자 : 시작 2, 종료 1  (분자는 감소)

=> 분모 : 시작 1, 종료 2  (분모는 증가)

  if(i % 2){  // 홀수 라인 - 밑에서 대각선으로 위로 숫자 변화
    ja = 1 + diff; // 분모가 1로 시작 i로 종료.
    mo= i - diff; // 분자가 i로 시작, 1로 종료.
  }
  else { // 짝수 라인 - 위에서 왼쪽 대각선으로 아래로 숫자 변화
    ja = i - diff; // 분모 i로 시작 1로 종료
    mo = 1 + diff; // 분자 1로시작 i로 종료
  }

---

풀릴 듯 안풀려서 고생했다.  나중에 다시 풀기!!!

참고 포스팅