Loading [MathJax]/jax/output/CommonHTML/jax.js
반응형

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

 

13975번: 파일 합치기 3

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수를 입력받을 때 priority_queue에 오름차순으로 넣습니다.

 

2. pq에서 맨 앞의 두 수를 뽑아 더한 값을 ans에 더하고, 그 값을 다시 pq에 넣습니다.

 

3. pq가 빌 때까지 위 과정을 반복합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#define ll long long
 
using namespace std;
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int K;
        scanf("%d", &K);
 
        priority_queue<ll, vector<ll>, greater<ll>> pq;
 
        ll ans = 0;
 
        for (int i = 0; i < K; i++) {
            ll num;
            scanf("%lld", &num);
 
            pq.push(num);
        }
 
        while (1) {
            const ll a = pq.top();
            pq.pop();
            const ll b = pq.top();
            pq.pop();
 
            ans += a + b;
 
            if (pq.empty()) break;
 
            pq.push(a + b);
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
[ 백준 ] 16562번 - 친구비 (C++)  (0) 2023.01.09
[ 백준 ] 14226번 - 이모티콘 (C++)  (0) 2023.01.08
반응형

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

 

17497번: 계산기

첫 번째 줄에 버튼을 누른 횟수 K (0 ≤ K ≤ 99) 를 출력합니다. 누른 횟수를 최소화 하지 않아도 됩니다. 단, 누른 횟수가 99번을 넘으면 안됩니다. 만약 99번 안에 N을 만드는 방법이 존재하지 않는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N에서부터 시작해 연산을 해주고 ans vector에 push 해줍니다.

 

2. 만약 N & 1일 경우 무조건 나눈 경우이므로 ans에 '/'를 push 하고 나누기 전 값인 N *= 2를 해줍니다.

 

3. 만약 N & 2일 경우 무조건 2를 더한 경우이므로 ans에 '+'를 push 하고 더하기 전 값이 N -= 2를 해줍니다.

 

4. 만약 2, 3 둘 다 아닐 경우 2를 곱한 경우이므로 ans에 '*'를 push 하고 곱하기 전 값인 N /= 2를 해줍니다.

 

5. N이 0이 되면 반복문을 탈출합니다.

 

6. ans에 추가된 연산자를 뒤에서부터 출력해 줍니다.

 

[ 소스코드 ]

 

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>
#include<vector>
#define ll long long
 
using namespace std;
 
ll N;
vector<char> ans;
 
int main()
{
    scanf("%lld", &N);
 
    while (N) {
        if (N & 1) {    //무조건 2로 나눈 경우
            ans.push_back('/');
            N *= 2;
        }
        else if (N & 2) {    //무조건 2를 더한 경우
            ans.push_back('+');
            N -= 2;
        }
        else {    //무조건 2를 곱한 경우
            ans.push_back('*');
            N /= 2;
        }
    }
 
    if (ans.size() > 99) {
        printf("-1");
    }
    else {
        printf("%d\n", ans.size());
        for (int i = ans.size() - 1; i >= 0; i--) {
            printf("[%c] ", ans[i]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
[ 백준 ] 17244번 - 아맞다우산 (C++)  (0) 2022.12.31
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
[ 백준 ] 1194번 - 달이 차오른다, 가자. (C++)  (0) 2022.12.28
[ 백준 ] 2589번 - 보물섬 (C++)  (0) 2022.12.27
반응형

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

 

2812번: 크게 만들기

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. stack에 가장 첫 번째 숫자를 넣습니다.

 

2. 이후 for문을 돌면서 stack.top()과 arr [ i ]를 비교합니다.

 

3. stack.top() < arr [ i ] 이면 stack.top() >= arr [ i ]가 될 때까지 stack.pop()을 해줍니다.

 

4. 이후 stack에 arr [ i ]를 push 해줍니다.

 

5. ans에 stack에서 하나씩 뽑아 저장해 준 후 for문을 돌면서 하나씩 출력해줍니다.

 

[ 소스코드 ]

 

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
#include<iostream>
#include<stack>
 
using namespace std;
 
int N, K;
char arr[500001];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    scanf("%s", arr);
 
    stack<int> s;
    stack<int> ans;
    s.push(arr[0] - '0');
 
    int cnt = 0;
 
    for (int i = 1; i < N; i++) {
        while (!s.empty()) {
            if (s.top() < arr[i] - '0' && cnt < K) {
                s.pop();
                cnt++;
            }
            else break;
        }
        s.push(arr[i] - '0');
    }
 
    while (!s.empty()) {
        ans.push(s.top());
        s.pop();
    }
 
    for (int i = 0; i < N - K; i++) {
        printf("%d", ans.top());
        ans.pop();
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1365번 - 꼬인 전깃줄 (C++)  (0) 2022.12.16
[ 백준 ] 16397번 - 탈출 (C++)  (0) 2022.12.15
[ 백준 ] 9019번 - DSLR (C++)  (0) 2022.12.13
[ 백준 ] 2665번 - 미로만들기 (C++)  (0) 2022.12.12
[ 백준 ] 1726번 - 로봇 (C++)  (0) 2022.12.11
반응형

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

 

2195번: 문자열 복사

첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. for문을 통해서 P문자열의 처음부터 끝까지 돌면서 S문자열과 비교합니다.

 

2. P문자열과 S문자열의 문자가 같으면 S문자열의 idx를 하나씩 증가시키면서 가장 긴 문자열을 찾고 max에 갱신시켜줍니다.

 

3. for문에서 i값을 max-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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int lenS, lenP;
char S[1001];
char P[1001];
 
int main()
{
    scanf("%s %s", S, P);
    
    lenS = strlen(S);
    lenP = strlen(P);
 
    int cur = 0;
    int ans = 0;
 
    for (int i = 0; i < lenP; i++) {
        int Max = 0;
        for (int j = 0; j < lenS; j++) {
            int cnt = 0;
            int a = 0;
            while (S[j+a] == P[i+a]) {
                if (S[j + a] == 0) break;
                cnt++;
                a++;
            }
            Max = max(Max, cnt);
        }
        i += Max-1;
        ans++;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2281번 - 데스노트 (C++)  (0) 2022.11.09
[ 백준 ] 7569번 - 토마토 (C++)  (0) 2022.11.08
[ 백준 ] 2253번 - 점프 (C++)  (0) 2022.11.06
[ 백준 ] 14002번 - 가장 긴 증가하는 부분 수열 4 (C++)  (0) 2022.11.05
[ 백준 ] 1577번 - 도로의 개수 (C++)  (0) 2022.11.04
반응형

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

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

끝나는 시간이 짧은 회의일수록 더 많은 회의에 참여할 수 있고, 끝나는 시간이 짧은 회의 중 시작하는 시간이 가장 빠른 회의를 하나씩 넣어가면서 문제를 풀었습니다.

 

1. 끝나는 시간이 짧은 회의일수록, 그중 시작하는 시간이 가장 빠른 회의일수록 앞으로 배치되게 정렬합니다.

 

2. 가장 앞에 있는 회의를 이전 회의의 끝나는 시간과 비교하여 이전 회의의 끝나는 시간보다 회의의 시작시간이 더 늦다면 ans를 1씩 더해줍니다.

 

3. 방금 시작한 회의의 끝나는 시간을 cur변수에 갱신시켜줍니다.

 

4. ans를 출력해줍니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct conference {
    int start;
    int end;
};
 
bool cmp(conference left, conference right) {        //정렬 순서
    if (left.end == right.end) return left.start < right.start;    //시작 시간이 빠를수록
    return left.end < right.end;    //끝나는 시간이 빠를수록
}
 
int N;
conference arr[100000];
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &arr[i].start, &arr[i].end);
    }
 
    sort(arr, arr + N, cmp);
 
    int cur = 0;
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        if (cur <= arr[i].start) {
            cur = arr[i].end;
            ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
반응형

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

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. Ai=Ai−1의 배수이므로 큰 수부터 K에 값을 빼가면서 ans의 값을 1씩 더해줍니다.

 

2. K가 0이 될 때 ans를 출력해주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, K;
int arr[10];
int ans;
 
int main()
{
    scanf("%d %d", &N, &K);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = N - 1; i >= 0; i--) {
        while (K >= arr[i]) {
            K -= arr[i];
            ans++;
        }
        if (K == 0) break;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 14889번 - 스타트와 링크 (C++)  (0) 2022.08.18
[ 백준 ] 11727번 - 2xn 타일링 2 (C++)  (0) 2022.08.17
[ 백준 ] 14499번 - 주사위 굴리기 (C++)  (0) 2022.08.16
반응형

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

 

17371번: 이사

(23,13)으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 2√23이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 10√23이다. 두 거리의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

생각을 조금만 해보면 쉽게 풀 수 있는 문제입니다.

 

점들 중 하나를 골라 다른 점들과 거리를 비교했을 때 가장 가까운 점은 거리가 0, 가장 먼 거리가 d일 때 평균 거리는 d2입니다. 따라서 이들 중 가장 짧은 거리를 구해주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<cmath>
 
using namespace std;
 
int N;
 
struct pos {
    int x;
    int y;
};
 
pos arr[1000];
int ans;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    double minDist = 9999999;
 
    for (int i = 0; i < N; i++) {
        int x = 0; int y = 0;
        double maxDist = 0;
        for (int j = 0; j < N; j++) {    //i번째 점부터 j번째 점까지 거리 중 가장 먼 거리를 maxDist에 저장
            double dist = sqrt(pow(arr[i].x - arr[j].x, 2) + pow(arr[i].y - arr[j].y, 2));
            maxDist = max(maxDist, dist);
        }
        
        if (minDist > maxDist) {        //maxDist 중 가장 짧은 거리를 minDist에 저장하고 idx를 ans에 저장
            ans = i;
            minDist = maxDist;
        }
    }
 
    cout << arr[ans].x << " " << arr[ans].y;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1708번 - 볼록 껍질 (C++)  (0) 2022.07.17
[ 백준 ] 1086번 - 박성원 (C++)  (0) 2022.07.15
[ 백준 ] 14428번 - 수열과 쿼리 16 (C++)  (0) 2022.07.13
[ 백준 ] 13977번 - 이항 계수와 쿼리 (C++)  (0) 2022.07.12
[ 백준 ] 11689번 - GCD(n, k) = 1 (C++)  (0) 2022.07.11
반응형

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

 

14939번: 불 끄기

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄

www.acmicpc.net

 

 

[ 문제풀이 ]

 

처음엔 dfs를 활용해서 풀었으나 100%에서 계속 틀렸습니다가 떠서 비트 마스킹으로 풀었습니다.

 

첫 줄의 스위치를 누르는 모든 경우의 수를 구한 후 arr [ i - 1][ j ]의 전구가 켜져 있다면 arr [ i ][ j ]의 스위치를 눌러서 끄고, 마지막에 마지막 줄에 전구가 다 꺼져있다면 불을 끌 수 있는 경우이므로 이때의 cnt를 출력해주면 됩니다.

 

[ 소스 코드 ]

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
99
100
101
102
103
104
105
106
107
#include<iostream>
 
using namespace std;
 
char arr[10][10];
char temp[10][10];
int dy[5] = { -1,1,0,0,0 };
int dx[5] = { 0,0,0,-1,1 };
int cnt;
int ans = 999;
 
void turn(int y, int x)        //스위치를 누르면 상태 변경
{
    for (int i = 0; i < 5; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy >= 0 && yy < 10 && xx >= 0 && xx < 10) {
            if (temp[yy][xx] == 'O') {
                temp[yy][xx] = '#';
            }
            else {
                temp[yy][xx] = 'O';
            }
        }
    }
}
 
int check()        //전구를 다 끌 수 있는지 체크 후 0 또는 1 return
{
    for (int i = 1; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (temp[i - 1][j] == 'O') {
                turn(i, j);
                cnt++;
            }
        }
    }
 
    for (int i = 0; i < 10; i++) {
        if (temp[9][i] == 'O') {
            return 0;
        }
    }
 
    return 1;
}
 
 
//void dfs(int level)
//{
//    if (level == 10) {
//        int ch = check(cnt);
//        if (ch) {
//            ans = min(ans, ch);
//        }
//        return;
//    }
//
//    for (int i = 0; i < 2; i++) {
//        if (i == 0) {
//            turn(0, level, arr);
//            cnt++;
//            dfs(level + 1);
//            turn(0, level, arr);
//            cnt--;
//        }
//        else {
//            dfs(level + 1);
//        }
//    }
//}
 
int main()
{
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int t = 0; t < 1024; t++) {        //모든 경우의 수
        cnt = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                temp[i][j] = arr[i][j];
            }
        }
 
        for (int i = 0; i < 10; i++) {
            if (t & (1 << i)) {
                turn(0, i);
                cnt++;
            }
        }
 
        if (!check()) continue;        //check()가 0이면 continue
 
        ans = min(ans, cnt);
    }
 
    if (ans == 999) {
        cout << -1;
    }
    else {
        cout << ans;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21

+ Recent posts

티스토리툴바