[모의 테스트 풀이] 분수찾기

안녕하세요! 모의테스트 푸시느라 고생 많으셨습니다.

문제가 맵지 않았나요? 

사실, 좀 어려운 문제들이었어요. 알고리즘에 대한 깊은 이해가 필요한 문제들이었습니다.

못푸셨다고 좌절할 필요 없어요(저도 다 못풀어요)!

 

그럼 풀이를 시작하겠습니다!

 

www.acmicpc.net/problem/1193

1193번: 분수찾기

예시로 주어진 그림을 자세히 보면, 대각으로 규칙이 있습니다.

빨간 대각 선을 기준으로, 분자와 분모의 합은 같습니다.

 

우리가 찾아낸 규칙을 통해 다음과 같은 규칙을 생각해 볼 수 있을 것 같습니다.

 

1. 우리가 찾을 X번째의 대략적인 위치를 찾는다. (분모 + 분자를 통해서 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, . . .)

2. 대략적으로 찾은 위치에서 분자/분모를 하여 분자가 1 ~ n까지 분모는 n ~ 1까지 하여 X의 위치를 찾아냅니다.

 

코드는 다음과 같습니다.

#include<stdio.h>

int main()
{
   int user_input;//사용자가 입력한 수
   int total = 0;//분수, 분모 더한 값의 위치를 찾는 수
   int pos;//분수 내에서 위치찾는 수
   int save = 1;//분수 저장값
   int i = 1, j = 1;
   scanf("%d", &user_input);
   while (total < user_input) {//분수, 분모 더한 값의 위치를 찾기
      total = total + i;
      i++;
   }
   pos = total - user_input;
   if ((i - 1) % 2 != 0) {//홀수 분수 내에서 위치 찾기
      if (pos != 0) {
         for (; pos != 0; pos--, j++) {
            save = i - j - 1;
         }
         printf("%d/%d", j, save);
      }
      else printf("1/%d", i - 1);
   }
   else {//짝수 분수 내에서 위치 찾기
      if (pos != 0) {
         for (; pos != 0; pos--, j++) {
            save = i - j - 1;
         }
         printf("%d/%d", save, j);
      }
      else printf("%d/1", i - 1);
   }
}