Round 171

시도했던 문제

- B. 수강변경 https://www.acmicpc.net/problem/23305

- C. 눈덩이 굴리기 https://www.acmicpc.net/problem/23305

- D. 2xN 예쁜 타일링 https://www.acmicpc.net/problem/18230

수강변경 - 성공 

먼저 바꾸고자 하는 수업 개수를 전부 센다.

다음으로 바꾸고싶은 수업이 있으면 count-- 한다.

수업 개수가 이미 0이라면 원하는 수업을 수강하지 못하는 학생이므로 ans++ 한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int v[1000005];

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        v[a]++;
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        
        if (v[a] == 0)
            ans++;
        else
            v[a]--;
    }
    
    printf("%d\n", ans);
    
    
    return 0;
}

눈덩이 굴리기 - 실패

재귀로 눈덩이를 +1칸으로 굴리는 경우 / +2칸으로 던지는 경우 두 경우를 모두 확인한 다음에 최대를 구하면 되겠다 싶었다. 

각 함수마다 2개의 분기가 생기고 트리의 높이는 최대 대회의 시간만큼이다.

2 ^ 10이라 시간복잡도 안에 충분히 돌 수 있다.

 

맞을 것 같았지만 틀렸다. 뭔가 꼬였다 싶어서 나중에 다시 확인해봐야지 싶었다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int v[1000005];
int n, m;

int solve(int idx, int m) {
    if (n < idx || m < 0)
        return 0;
    
    return max(v[idx] + solve(idx + 1, m - 1) , v[idx] / 2 + solve(idx + 2, m - 1));
}

int main() {
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    
    v[0] = 1;
    cout << solve(0, m);
    
    
    return 0;
}

 

2xN 예쁜 타일링 - 성공

예쁨이 큰 것부터 타일을 차곡차곡 쌓으면 된다. 

2 * 1인 타일 두 개로 2 * 2 타일을 만들 수 있으므로 타일을 합쳐서 생각했다. 

 

로직

- 홀수인 경우 가장 예쁜 2 * 1 타일을 하나 끼운다

- 2 * 1 타일 두 개를 합쳐 2 * 2 타일을 만든다

- 2 * 2 타일을 정렬해서 가장 큰 것부터 끼운다

 

2 * 1을 먼저 끼우는 경우 남은 타일을 만드는게 조금 헷갈렸다. 

타일 하나 없는거 생각 못하고 구현해서 인덱스 아웃 오브 바운드 뜨고,,, 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;


int main() {
    int n, a, b;
    scanf("%d %d %d", &n, &a, &b);
    
    vector<int> va(a);
    for (int i = 0; i < a; i++)
        scanf("%d", &va[i]);
    vector<int> vb(b);
    for (int i = 0; i < b; i++)
        scanf("%d", &vb[i]);
    
    sort(all(va), greater<int>());
    
    i64 ans = n % 2 == 0 ? 0 : va[0];
    for (int i = n % 2; i + 1 < a; i += 2) {
        vb.push_back(va[i] + va[i + 1]);
    }
    
    sort(all(vb), greater<int>());
    
    for (int i = 0; i < n/2; i++) {
        ans += vb[i];
    }
    
    printf("%lld", ans);
    
    
    return 0;
}

업솔빙

- C. 눈덩이 굴리기 https://www.acmicpc.net/problem/23305

- E. 플로이드에 오타가? https://www.acmicpc.net/problem/13314

 

눈덩이 굴리기

 

 

 

 

 

 

플로이드에 오타가?