반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 수학

2. 시뮬레이션


이 문제는 따로 알아야 될 알고리즘은 없고 , 


시간 및 공간복잡도의 제약을 받지 않지만 수학적 사고를 요구하는 문제이다.


모든 내용은 소스 코드의 주석으로 달아두었다.


소스 코드 : 


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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
 
using namespace std;
 
int main() {
    int n, val[50], a, b;
    
    cin >> n;
 
    bool flag = false;
    for (int i = 0; i < n; i++)
        cin >> val[i];
 
    // 수가 1개면 무조건 A
    if (n == 1
        cout << "A";
 
    // 수가 2개면 두수가 같지 않다면 A출력
    else if (n == 2
    {
        if (val[0== val[1])
            cout << val[0];
 
        else
            cout << "A";
    }
 
    // 3이상 일 때
    else 
    {
 
        // 처음수와 다음수가 같을 때
        if (val[0== val[1]) 
        {
            for (int i = 2; i<n; i++
            {
                // 처음수와 같지 않은 다른수가 있다면
                if (val[i] != val[0]) 
                    flag = true;
            }
            
            // 답을 알 수 없다.
            if (flag) 
                cout << "B";
            
            // 처음수와 값이 계속 같았다면 처음수 출력
            else 
                cout << val[0];
        }
 
        // 처음수와 다음수가 다를 때
        else 
        {
            // 다음수와 그다음 수가 같을 때
            if (val[1== val[2]) 
            {
                a = 0;
                b = val[1];
            }
 
            // 처음수, 다음수, 그다음수 모두 다를 때
            else 
            {
                // 나머지가 0이 아니라면 답을 구할 수 없다.
                if ((val[1- val[2]) % (val[0- val[1]) != 0
                    flag = true;
                
                // 나머지가 0이라면 a와 b를 구할 수 있다.
                else 
                {
                    a = (val[1- val[2]) / (val[0- val[1]);
                    b = val[1- a*val[0];
                }
            }
 
            // 여전히 답을 구할 수 있다는 여지가 있을 때
            if (flag == false
            {
                // 마지막 검사를 한다 예를들어 1 2 3 4 6 6 같은 수
                for (int i = 3; i < n; i++
                {
                    if (val[i] != val[i - 1* a + b) flag = true;
                }
            }
 
            if (flag) 
                cout << ("B");
 
            else 
                cout << val[n - 1* a + b;
        }
    }
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[11051번] 이항 계수 2  (2) 2016.11.02
[1193번] 분수찾기  (0) 2016.11.02
[13419번] 탕수육  (0) 2016.10.31
[13417번] 카드 문자열 (Deque 활용)  (3) 2016.10.31
[9094번] 수학적 호기심  (0) 2016.10.31