백준 알고리즘 단계별로 풀어보기/기본수학1

[백준 알고리즘 1193번 문제] 분수찾기 (C언어) #브론즈Ⅰ

MNMNWVWV 2023. 1. 24. 17:50
728x90
반응형
브론즈Ⅰ

 

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

 

1193번: 분수찾기

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

www.acmicpc.net

 

 

 

풀이 방법

 

위의 분수를 

1/1

1/2  2/1

3/1  2/2  1/3

1/4  2/3  3/2  4/1

5/1  4/2  3/3  2/4  1/5

...

다음과 같이 규칙에 따라 각 줄로 나타낼 수 있다.

여기서 식 k(k+1)/2를 이용해 주어지는 값 X가 위의 줄에서 몇번째 줄인지를 알 수 있다.

 

짝수번째 줄 : 분자 - 오름차순, 분모 - 내림차순
홀수번째 줄 : 분자 - 내림차순, 분모 - 오름차순

 

위의 규칙에 따라 내가 작성한 수식에 값을 대입하여 적절한 output 값을 출력한다.

 

내 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#pragma warning(disable:4996)
#include <stdio.h>
 
int FindLine(int n);
int ASCN(int k, int n);
int DESCN(int k, int n);
 
int main(void) {
    int i, j, k, n;
    int num, dnum; //분자 분모
 
    scanf("%d"&amp;n);
 
    k = FindLine(n);
    
    //짝수번째 줄 : 분자 - 오름차순, 분모 - 내림차순
    //홀수번째 줄 : 분자 - 내림차순, 분모 - 오름차순
    if (k % 2 == 0) {
        num = ASCN(k, n);
        dnum = DESCN(k, n);
    }
    else {
        num = DESCN(k, n);
        dnum = ASCN(k, n);
    }
    printf("%d/%d\n", num, dnum);
    
    return 0;
}
 
int FindLine(int n) {
    int k;
    for (k = 1;; ++k) {
        if ((k) * (k + 1/ 2 &gt;= n &amp;&amp; n &gt; (k - 1* (k) / 2) {
            return k;
        }
    }
}
 
int ASCN(int k, int n) {
    int out;
 
    out = n - ((k - 1* (k) / 2);
 
    return out;
}
 
int DESCN(int k, int n) {
    int out;
 
    out = ((k) * (k + 1/ 2- n + 1;
    
    return out;
}
cs

 

느낀점

 

딱히 없다.

728x90
반응형