백준 1193 번 문제 풀이 C++ :분수찾기

#58. 백준 1193번 문제 풀이: 분수찾기

배열에 다음과 같이 분수들이 적혀있다. 배열을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → …와 같이 지그재그로 ①②③④⑤..순서를 가진다 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

①1/1	②1/2	⑥1/3	⑦1/4	...
③2/1	⑤2/2	⑧2/3	⑭2/4	...
④3/1	⑨3/2	⑬3/3	...	...
⑩4/1	⑫4/2	...	...	...
⑪5/1	...	...	...	...
...	...	...	...	...

입력: 첫줄에 X 출력 분수값

입력/출력

--입력--
1
--출력--
1/1
--입력--
2
--출력--
1/2
--입력--
3
--출력--
2/1
--입력--
14
--출력--
2/4

문제풀이+해설

이번 문제는 규칙을 찾아 수학적으로 판단하는 센스가 필요하다.
지그재그의 사선 라인을 보면,
1번사선 ①
2번사선 ②③
3번사선 ④⑤⑥
4번사선 ⑦⑧⑨⑩
...
N번사선에는 N개의 항목가 존재한다.
즉, 순서번호가 주어졌을 때, 위의 항목개수를 합하다가 n보다 커지면 찾는 사선번호가 된다.
항목의 핪에서 - 순서번호를 빼면, 해당 사선번호 내 상대위치를 알 수 있다.
짝수, 홀수 사선번호가 서로 반대의 방향이므로, 짝/홀을 나누어 계산한다.
짝수일 경우 분자: 사선번호 - 상대위치, 분모: 상대위치 +1
홀수일 경우 분자: 상대위치 + 1, 분목: 사선번호 - 상대위치
가 된다.

예를 들면, 
1) 순서값을 2 를 주었다면,
2) +1, +2 항목 두번을 더하는 루프를 돌리면 항목합이 3 이되어 2보다 크므로 사선번호는 2
3) 사선내 상대위치는 항목합(3) 에서 순서번호(2)를 빼면 1
4) 2번사선이 짝수사선이므로 분자는 사선번호(2) - 상대위치(1) = 1, 분모는 상대위치(1) + 1 = 2
5) 답은 "분자/분모" 문자열 이므로 "1/2"

code sol.

코드편집/실행

#include <iostream>
using namespace std;

int main() {
  int x, line, n, d, p1, p2;
  cin >> x; // 찾을값을 가진 순서값을 받음
  line = 0; // 사선번호 카운트
  n = 0; // 항목(배열) 개수 합
  while(n < x) { // 항목합이 순서값보다 크면 루프 끝냄
    line += 1; // 루프 돌 때 마다 사선번호 카운트
    n += line ; // 1, 2, 3, 4.. 사번번호 항목수가 있으므로 더해줌
  } // 루프가 끝나면 line 값이 순서값이 존재하는 사선번호가 된다.
  d = n - x; // 사선번호까지 항목합과 순서값의 차이값 계산.
  if(line % 2 == 0) { // 사선번호가 짝수일 경우
    p1 = line - d; // 사선번호에서 차이값을 빼주면 분자값
    p2 = d + 1; // 차이값 +1 은 분모값
  } else { // 사선번호가 홀수일 경우
    p1 = d + 1; // 차이값 +1 은 분자값
    p2 = line - d; // 사선번호에 차이값을 더하면 분모값
  }
  cout << p1 << "/" << p2; // 결과값 "분자/분모" 출력
  return 0;
}