문제 풀이

 

 에라토스테네스의 체를 활용하여 소수를 구했습니다.

(https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)

 

 

코드

 

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
#include <iostream>
#include <vector>
 
using namespace std;
 
int d[1001] = { 0, };
 
int main() {
 
    int n;
    int m = 0;
    cin >> n;
 
    vector <int> v;    
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if(x > m)
            m = x;
        v.push_back(x);
    }
    
    d[1] = 1;
    for (int i = 2; i <= m; i++)
    {
        if (d[i] == 0)
        {
            for (int j = i; j*i <= m; j++)
            {
                if (d[j*i] == 0)
                    d[j*i] = 1;
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (d[v[i]] == 0)
            ans++;
    }
 
    cout << ans;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

1978번: 소수 찾기

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

14500번: 테트로미노 (백준 온라인 저지, C++)  (0) 2019.04.03
2448번: 별 찍기 - 11 (백준 온라인 저지, C++)  (0) 2019.04.02
2108번: 통계학 (백준 온라인 저지, C++)  (0) 2019.04.02
1427번: 소트인사이드 (백준 온라인 저지, C++)  (0) 2019.04.01
2750번: 수 정렬하기 (백준 온라인 저지, C++)  (0) 2019.04.01

문제 해설

 

 자료형을 연습하기 좋은 문제라고 생각이 들어 가져오게 되었습니다. 유의해야 할 점은 총 두 가지로 반올림과 최빈값 구하기입니다.

 반올림 같은 경우, 양수와 음수일 때를 고려하여 양수일 때는 0.5를 더해준 값을 int형으로 변환시켜 저장해 주었고 음수일 때는 0.5를 빼준 값을 int형으로 변환시켜 저장하였습니다. 최빈값의 경우, 우선 가장 빈도수가 높을 때 빈도가 몇인지 구하여 같은 빈도가 있는지 확인해 주었습니다.

 

 

코드

 

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
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int d[500000];
 
int main() {
 
    int n;
    int bi[8001] = { 0, };
    int sum = 0, bm = 0, cm = 0, dm = 0;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &d[i]);
        sum += d[i];
 
        int x = d[i] + 4000;
        bi[x]++;
    }
 
    sort(d, d + n);
 
    int maximum = 0;
    for (int i = 0; i <= d[n - 1] + 4000; i++)
    {
        if (bi[i] > maximum)
            maximum = bi[i];
    }
 
    vector <int> v;
    for (int i = 0; i <= d[n - 1] + 4000; i++)
    {
        if (bi[i] == maximum)
            v.push_back(i);
    }
 
    float am = float(sum) / float(n);
 
    if (am >= 0)
        am = int(am + 0.5);
    else
        am = int(am - 0.5);
 
    bm = d[n / 2];
 
    if (v.size() > 1)
        cm = v[1] - 4000;
    else
        cm = v[0] - 4000;
 
    dm = d[n - 1] - d[0];
 
    printf("%d\n", int(am));
    printf("%d\n", bm);
    printf("%d\n", cm);
    printf("%d\n", dm);
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

2108번: 통계학

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2448번: 별 찍기 - 11 (백준 온라인 저지, C++)  (0) 2019.04.02
1978번: 소수 찾기 (백준 온라인 저지, C++)  (0) 2019.04.02
1427번: 소트인사이드 (백준 온라인 저지, C++)  (0) 2019.04.01
2750번: 수 정렬하기 (백준 온라인 저지, C++)  (0) 2019.04.01
6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31

문제 풀이

 

 다양한 방법으로 풀이가 가능한 문제로 저는 포인터를 역 방향으로 참조하여 문제를 풀었습니다.

 

 

코드

 

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string d;
    cin >> d;
    sort(d.rbegin(), d.rend());
    cout << d;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

 

1427번: 소트인사이드

첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1978번: 소수 찾기 (백준 온라인 저지, C++)  (0) 2019.04.02
2108번: 통계학 (백준 온라인 저지, C++)  (0) 2019.04.02
2750번: 수 정렬하기 (백준 온라인 저지, C++)  (0) 2019.04.01
6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31
1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31

문제 해설

 

 단순한 정렬 문제입니다. 버블 소트를 활용하여 풀이하였습니다.

 

 

코드

 

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
#include <iostream>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    int d[1000];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> d[i];
 
    //bubble sort
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (d[j] > d[j + 1])
            {
                int tmp = d[j];
                d[j] = d[j + 1];
                d[j + 1] = tmp;
            }
        }
    }
 
    for (int i = 0; i < n; i++)
        cout << d[i] << '\n';
 
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2108번: 통계학 (백준 온라인 저지, C++)  (0) 2019.04.02
1427번: 소트인사이드 (백준 온라인 저지, C++)  (0) 2019.04.01
6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31
1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31
2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31

문제 풀이

 

 이 문제는 단순히 구현을 했을 때는 시간 초과가 나게 됩니다. 따라서 x를 고정시켜 주고, 이 x에 따라 나올 수 있는 y를 찾아가면서 문제를 풀어야 합니다.

 

 예를 들어, 10 12 3 9의 경우 3이 x의 자리에 올 때 y의 자리에 올 수 있는 값은 3, 1, 11, 9, ... 이며 이 때 각각 10년의 텀을 두고 발생하게 됩니다. 따라서 답은 3년에 3*10을 더한 33년이 됩니다. 주의할 점은 % 연산의 경우 0부터 시작하기 때문에 이를 고려하여 코드를 구성해야 합니다.

 

 만약 가장 처음에 y 자리에 왔던 값이 다시 나타나게 된다면, 이는 한 주기를 모두 지났다는 뜻이 되므로 종말 년도를 넘어섰다는 뜻이 됩니다. 따라서 -1을 출력합니다.

 

 또는 최소 공배수와 최대 공약수를 활용하여 종말 년도를 먼저 계산하고, 이를 넘어서는 경우를 찾아주는 것도 가능합니다.

 

 

코드

 

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
#include <iostream>
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    cin >> t;
 
    while (t--)
    {
        int m, n, x, y;
        cin >> m >> n >> x >> y;
 
        int ans = x, b = (x - 1) % n + 1;
        int tmp = b;
 
        while (1)
        {
            if (b == y)
                break;
            
            b = (b + m - 1) % n + 1; 
            ans += m;
 
            if (tmp == b)
            {
                ans = -1;
                break;
            }
        }
 
        cout << ans << "\n";
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

6064번: 카잉 달력

문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1427번: 소트인사이드 (백준 온라인 저지, C++)  (0) 2019.04.01
2750번: 수 정렬하기 (백준 온라인 저지, C++)  (0) 2019.04.01
1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31
2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31
5622번: 다이얼 (백준 온라인 저지, C++)  (0) 2019.03.31

풀이

방 번호 문제의 경우, 6과 9가 겹치는 부분만 처리해주면 크게 어렵지 않은 문제입니다.

문자를 하나 하나 비교하여 배열을 증가시키는 경우 코드가 길어지기 때문에 '0'의 아스키 코드 값이 48인 것을 활용하여 문제를 풀었습니다. 또는 int형으로 숫자를 입력받고 10으로 0이 될 때까지 나누어 나머지 값을 인덱스로 참조하여 배열을 증가시켜 주는 방법도 가능합니다.

 

코드

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
#include <cstdio>
 
using namespace std;
 
int main() {
 
    int a[9] = { 0, };
    char line[8];
    scanf("%s", &line);
 
    int i = 0;
    while (line[i])
    {
        int x = line[i] - 48;
        if (x == 9)
            a[6]++;
        else
            a[x]++;
        i++;
    }
    
    a[6] = (a[6] + 1) / 2;
 
    int m = 0;
    for (int i = 0; i < 10; i++)
    {
        if (a[i] > m)
            m = a[i];
    }
 
    printf("%d\n", m);
    
    return 0;
}

 

제출 결과

 

문제 출처

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

 

1475번: 방 번호

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2750번: 수 정렬하기 (백준 온라인 저지, C++)  (0) 2019.04.01
6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31
2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31
5622번: 다이얼 (백준 온라인 저지, C++)  (0) 2019.03.31
2908번: 상수 (백준 온라인 저지, C++)  (0) 2019.03.31

문제

 “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”

모든 거주자가 해당 계약 조건을 지키고 입주하였을 때, k층에 n호에는 몇 명이 살고 있는가? 단, 아파트는 0층부터 있고 각 층에는 1호부터 있으며 0층의 i호에는 i명이 산다.

 

입력

 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두번째 줄에 정수 n이 주어진다. (k와 n은 1에서 14까지의 정수)

 

출력

 각각의 Test case에 대해서 해당 집에 거주민 수를 출력.

 

코드

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
#include <iostream>
 
using namespace std;
 
int main() {
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL);
 
    int t;
    cin >> t;
 
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        
        int d[15][15] = { 0, };
        
        for (int i = 0; i <= n; i++)
        {
            for (int j = 1; j <= k; j++)
            {
                if (i == 0)
                    d[i][j] = j;
                else
                    d[i][j] = d[i][j - 1] + d[i - 1][j];
            }
        }
 
        cout << d[n][k] << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter
 
 

 

제출 결과

 

문제 출처

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

 

2775번: 부녀회장이 될테야

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31
1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31
5622번: 다이얼 (백준 온라인 저지, C++)  (0) 2019.03.31
2908번: 상수 (백준 온라인 저지, C++)  (0) 2019.03.31
2675번: 문자열 반복 (백준 온라인 저지, C++)  (0) 2019.03.31

입력

알파벳 대문자로 이루어진 단어

 

출력

다이얼을 걸기 위해 필요한 시간

 

문제 풀이

단순히 각각의 케이스를 if문으로 나열하는 것도 가능합니다. 그러나 코드가 길어지는게 싫었어요ㅠㅠ

그래서 A의 아스키 코드 값이 65인 것을 활용하여 문제를 풀었습니다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    char a[16];
    cin >> a;
    int ans = 0;
    for (int i = 0; a[i]; i++)
    {
        int x = a[i];
        if (x >= 90)
            x = (x - 67) / 3 + 3;
        else if (x >= 83)
            x = (x - 66) / 3 + 3;
        else
            x = (x - 65) / 3 + 3;
        ans += x;
    }
    cout << ans << '\n';
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

제출 결과

 

문제 출처

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

 

5622번: 다이얼

문제 상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다. 전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다. 숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해선 1초씩 더 걸린다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31
2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31
2908번: 상수 (백준 온라인 저지, C++)  (0) 2019.03.31
2675번: 문자열 반복 (백준 온라인 저지, C++)  (0) 2019.03.31
11654: 아스키 코드 (백준 온라인 저지, C++)  (0) 2019.03.30

+ Recent posts

티스토리툴바