2309번 문항 일곱 난쟁이 문항입니다.


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




제가 문제를 푼 순서입니다.


1. 아홉 난쟁이들을 우선 오름차순으로 정렬한다.

2. 두 난쟁이들을 제외하면서, 일곱 난쟁이들의 키의 합을 구한다.

3. 100이 되면 그 두 난쟁이들을 제외하고 일곱 난쟁이들을 출력한다.


라고 생각을 한 다음, 코드로 구현했습니다.


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
#include<iostream>
 
using namespace std;
 
bool add_shortguys(int a, int b, int * _shortguys)    //제외할 두 난쟁이의 index는 a,b입니다.
{
    int sum = 0;
    for (int i = 0; i < 9; i++)    
    {
        if (i == a || i == b) continue;                //두 난쟁이들을 제외하고
        sum += _shortguys[i];                        //합을 구합니다.
    }
    if (sum == 100) { return true; }                //총 합이 100이 되면 true값을 반환하고
    else return false;                                //100이 아니라면 false값을 반환합니다.
}
 
int main()
{
    int shortguys[9] = { 0 };
    int temp;
    for (int i = 0; i < 9; i++)
    {
        cin >> shortguys[i];
    }
 
    for (int j = 0; j < 8; j++)                        //우선 아홉난쟁이들을 오름차순으로 정렬합니다.
    {
        for (int i = 0; i < 9-(j+1); i++)
        {
            if (shortguys[i] > shortguys[i + 1])
            {
                temp = shortguys[i];
                shortguys[i] = shortguys[i + 1];
                shortguys[i + 1] = temp;
            }
        }
    }
 
    for (int i = 0; i < 8; i++)                        //모든 경우의 수를 순서대로, 두 난쟁이들을 선정합니다.
    {
        for (int j = i + 1; j < 9; j++)
        {
            if (add_shortguys(i, j, shortguys) == true)        //그렇게 선정된 난쟁이들을 만들어준 함수에 매개변수로 넘겨줍니다.
            {                                                //일곱 난쟁이들의 합이 100임을 확인하면, true값을 반환합니다.
                for (int k = 0; k < 9; k++)                    //제외했던 두 난쟁이들을 제외하고 일곱난쟁이들을 출력합니다.
                {
                    if (k == i || k == j) continue;
                    cout<< shortguys[k]<<"\n";
                }
                return 0;                                    //출력을 완료하고 프로그램을 종료시켜야합니다.(유의하세요)
            }
        }
    }
    return 0;
}
cs



정답확인했습니다.

저작자표시

'백준 문제풀이 (C++) > 브루트 포스' 카테고리의 다른 글

[브루트 포스] 1476번 날짜 계산 풀이법  (0) 2020.08.23

 


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



이 문제 역시 유클리드 호제법으로 풀 수 있습니다. 

https://haula.tistory.com/entry/%E3%85%81 <- 여기서 자세한 알고리즘 설명을 확인 하실 수 있습니다.


여기서 주의할 것은 자료형입니다.

입력으로 주어지는 수는 범위가 1,000,000까지 입니다.

총 합의 범위는 10*99/2*1,000,000 이므로 49억입니다.

int형의 표현범위는 +-21억이며, unsigned int형의 표현범위는 +42억입니다.

따라서 이를 넘는 범위인 long long 형으로 선언해야합니다. (long long의 표현범위눈 +-900경입니다.)


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
#include<iostream>
 
using namespace std;
 
int gcd(int x, int y)
{
    if (x % y == 0) return y;
    else return gcd(y, x % y);
}
 
int main()
{
    int t, n;
    long long n_arr[101] = { 0 };
    long long sum[101] = { 0 };
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        for (int j = 0; j < n; j++)
        {
            cin >> n_arr[j];
        }
        for (int k = 0; k < n; k++)
        {
            for (int p = k + 1; p < n; p++)
            {
                sum[i] += gcd(n_arr[k], n_arr[p]);
            }
        }
    }
 
    for (int i = 0; i < t; i++)
    {
        cout << sum[i]<<"\n";
    }
}
cs




정답확인 완료하였습니다.



저작자표시

'백준 문제풀이 (C++) > 수학' 카테고리의 다른 글

[수학] 1934번 최소공배수 C++ 풀이법  (0) 2020.08.22
[수학] 2609번 최대공약수와 최소공배수 C++ <유클리드 풀이>  (0) 2020.08.22
[수학] 10430번 나머지  (0) 2020.08.21


1934번은 앞전에 풀었던 2609번과 유사한 방법으로 풀 수 있습니다.

최소공배수를 구하기 위해서는 최대공약수를 먼저 구한다음에, 두 수를 각각 최대공약수로 나눈 나머지와 최대공약수를 곱해주면 쉽게 구할 수 있습니다.


https://haula.tistory.com/entry/%E3%85%81


알고리즘이 궁금하신분은 여기서 확인하시면 됩니다.


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
#include<iostream>
 
using namespace std;
 
int divide(int x, int y)
{
    if (x % y == 0)
        return y;
    else
        return divide(y, x % y);
}
 
int main()
{
    int T;
    int A, B;
    cin >> T;
 
    for (int i = 0; i < T; i++)
    {
        cin >> A >> B;
        if (A >= B)
        {
            cout << A * B / divide(A, B) << "\n";
        }
        else
            cout << A * B / divide(B, A) << "\n"; 
    }
}
cs



정답처리 확인하였습니다. 감사합니다. 

저작자표시

'백준 문제풀이 (C++) > 수학' 카테고리의 다른 글

[수학] 9613번 GCD 합 C++ 풀이법  (0) 2020.08.22
[수학] 2609번 최대공약수와 최소공배수 C++ <유클리드 풀이>  (0) 2020.08.22
[수학] 10430번 나머지  (0) 2020.08.21


이 문제는 최소공배수와 최대공약수를 구하는 문제입니다. 

최대공약수를 구한다음, 주어진 수를 최대공약수로 나눈 뒤 나머지들을 최대공약수와 곱해주면 최소공배수를 구할 수 있습니다. 

그렇다면 최대공약수는 어떻게 구하면 될까요?


유클리드 알고리즘을 이용하면 됩니다. 


유클리드 호제법(=유클리드 알고리즘) 은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나입니다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의미합니다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 


쉽게 설명하자면, 

1. 큰수를 작은 수로 나눕니다.

2. 나누는 수를 나머지로 계속 나눕니다. 

3. 나머지가 0이 나올 때까지 반복합니다.

4. 나머지가 0이 나온다면 그 때 나누는 수가 최대공약수가 됩니다.


예시를 들어 설명드리겠습니다.

1512와 1008의 최대공약수를 구해봅시다.

우선 1512가 1008보다 크니까 1512를 1008로 나눠줍니다. 그럼 나머지가 504가 나오죠?

그럼 1008을 504로 나눠줍니다. 그럼 나머지가 0으로 떨어지죠

그렇다면 1512와 1008의 최대공약수는 504입니다.


1. 1512%1008=504

2. 1008%504=0

그렇다면 최대공약수는 504


이번엔 1440과 864의 최대공약수를 구해볼까요?

1440을 864로 나눠줍니다. 그럼 나머지는 576이 나오죠

그리고 864를 576으로 또 나눠줍니다.

나머지가 288이 나옵니다.

576을 다시 288로 나눠줍니다. 그럼 나머지가 0이나오죠. 그러면 288이 최대공약수가 됩니다.


1. 1440%864=576

2. 864%576=288

3. 576%288=0

따라서 최대공약수는 288


이해가 되시나요?!


그렇다면 왜 이런 방법이 성립되는지 증명을 해보도록하겠습니다.


그럼 코딩으로 구현해보겠습니다.


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
#include<iostream>
 
using namespace std;
 
int divide(int x, int y)
{
    if (x % y == 0)
    {
        return y;
    }
    return divide(y, x % y);
}
 
int main()
{
    int A, B;
    int common_max = 0;
    cin >> A >> B;
 
    if (A >= B)
    {
        common_max=divide(A, B);
    }
    else common_max=divide(B, A);
 
    cout << common_max << "\n";
    cout << A * B / common_max << "\n";
}
cs




정답입니다.

저작자표시

'백준 문제풀이 (C++) > 수학' 카테고리의 다른 글

[수학] 9613번 GCD 합 C++ 풀이법  (0) 2020.08.22
[수학] 1934번 최소공배수 C++ 풀이법  (0) 2020.08.22
[수학] 10430번 나머지  (0) 2020.08.21


백준 10430번 나머지 문제풀이



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
 
using namespace std;
 
int main()
{
    int A, B, C;
    cin >> A >> B >> C;
 
    cout << (A + B) % C<<"\n";
    cout << ((A % C) + (B % C)) % C << "\n";
    cout << (A * B) % C << "\n";
    cout << ((A % C) * (B % C)) % C << "\n";
 
    return 0;
}
cs


저작자표시

'백준 문제풀이 (C++) > 수학' 카테고리의 다른 글

[수학] 9613번 GCD 합 C++ 풀이법  (0) 2020.08.22
[수학] 1934번 최소공배수 C++ 풀이법  (0) 2020.08.22
[수학] 2609번 최대공약수와 최소공배수 C++ <유클리드 풀이>  (0) 2020.08.22

백준 10870번 피보나치수5 문제풀이


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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
 
using namespace std;
 
int fivo(int N)
{
    if (N == 0) return 0;
    if (N == 1) return 1;
    return fivo(N-1)+ fivo(N-2);
}
 
int main()
{
    int N;
    cin >> N;
 
    cout << fivo(N);
}
cs



저작자표시

'백준 문제풀이 (C++) > 재귀함수' 카테고리의 다른 글

[재귀함수] 10872번 팩토리얼 풀이 c++ (시간초과 에러 해결법)  (0) 2020.08.15

+ Recent posts

티스토리툴바