백준 및 코드포스

재밌는 그리디 문제이다.

종류가 다른 구슬을 2개씩 부딪혀 깰 수 있다고 할 때, 

최소한의 구슬을 남기는 문제다.

비슷한 문제로 자유 이용권 문제가 있다.

풀이 방법은,

가장 많은 개수의 구슬을 n, 나머지 총합을 m으로 뒀을 때

1. n > m 이라면 무조건 n - m 의 구슬은 남고, 나머지는 깰 수 있다.

2. n = m 이라면 0개의 구슬만 남는다.

3. n < m 이라면 전체 구슬이 홀수라면 1개가, 아니라면 0개가 남는다.

따라서 아래와 같이 작성할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
long long n, m,k,arr[100001];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>k;
    
    for(int i = 0; i < k; i++) cin>>arr[i];
    sort(arr, arr + k);
    
    n = arr[k - 1]; //최댓값
    for(int i = 0; i < k - 1; i++) {
        m += arr[i]; //나머지
    }
    if(n > m) cout<< n - m;
    else {
        if((n + m) % 2) cout<<1;
        else cout<<0;
    }
}

추가적으로

이 문제를 풀지 못해서 너무 스트레스 받는다..

실버 2의 마인크래프트를 어떻게 푸는지 모를 때의 기분과 같다.

문제에 적힌 순서대로 구현했다.

1. 낚시왕을 옮기고, 같은 열의 상어를 잡는다.

2. 상어를 옮기고, 그 상어의 위치를 임시로 저장한다. 나는 arr에 저장했다.

3. 옮긴 상어의 위치에 다른 상어가 있다면, 큰 상어만 남긴다.

4. 이동이 끝나면 arr에 임시로 저장돼있는 상어를 전부 map에 다시 옮겨준다.

위의 과정을 낚시왕이 1열에서 c열까지 이동할 때까지

즉, c번 반복하며 최종 점수를 출력하면 된다.

상어의 최대 속력은 1000으로, 나와 같이 while 문으로 모든 상어를 천 번씩 옮기면 TLE를 받는다.

따라서 모듈러 연산을 통해 양 벽을 부딪힌 후,

상어가 같은 방향, 같은 위치로 돌아올 경우에서부터 계산을 해주면 된다.

구현 문제인데, 문제가 친절하고 자세하게 설명돼있어 골드 1 문제같지는 않았다.

큰 상어만 남기는 아이디어가 힘들긴 했다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Shark {
    int R, C, speed, dir, sco;
};
vector<Shark> map[101][101];
vector<Shark> arr[101][101];
int dx[5] = {0, -1, 1, 1, -1}, score;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int r,c,m;
    cin>>r>>c>>m;
    for(int i = 0; i < m; i++) {
        struct Shark a;
        cin>>a.R>>a.C>>a.speed>>a.dir>>a.sco;
        if(a.dir == 1 || a.dir == 2) a.speed %= (r - 1) * 2;
        else a.speed %= (c - 1) * 2;
        map[a.R][a.C].push_back(a);
    }
    
    int fisher = 0, coun = c;
    while(coun--) {
        fisher++; //낚시왕 옮기기
        for(int i = 1; i <= r; i++) { //상어 잡기
            if(map[i][fisher].empty()) continue;
            score += map[i][fisher][0].sco;
            map[i][fisher].pop_back();
            break;
        }
        
        for(int i = 1; i <= r; i++) { //상어가 있다면 옮겨주기
            for(int j = 1; j <= c; j++) {
                if(map[i][j].empty()) continue;
                struct Shark t = map[i][j][0];
                int move = t.speed;
                if(t.dir == 1 || t.dir == 2) {
                    while(move--) {
                        if(t.R == 1) t.dir = 2;
                        if(t.R == r) t.dir = 1;
                        t.R += dx[t.dir];
                    }
                }
                else {
                    while(move--) {
                        if(t.C == 1) t.dir = 3;
                        if(t.C == c) t.dir = 4;
                        t.C += dx[t.dir];
                    }
                }
                
                if(arr[t.R][t.C].empty()) {//큰 상어만 남기기
                    arr[t.R][t.C].push_back(t);
                }
                else {
                    if(arr[t.R][t.C][0].sco < t.sco) {
                        arr[t.R][t.C].pop_back();
                        arr[t.R][t.C].push_back(t);
                    }
                }
            }
        }
        
        for(int i = 1; i <= r; i++) { //업데이트
            for(int j = 1; j <= c; j++) {
                map[i][j] = arr[i][j];
                if(!arr[i][j].empty()) arr[i][j].pop_back();
            }
        }
    }
    cout<<score;
}

bfs 문제이다.

{ 복사, 붙여넣기, 삭제 }의 3가지 경우의 수에 따라서 bfs를 돌려주면 된다.

나는 두 가지 방법으로 풀었다.

첫 번째 방법이다.

1. 미리 탐색을 끝마친다.

2. S개의 이모티콘을 만드는데에 가장 짧은 시간을 출력한다.

vis배열을 2차원으로 선언해서,

n개의 이모티콘이 클립보드에 있을 때

1000개의 이모티콘을 만드는 가장 짧은 시간을 탐색한다.

이 방법은 미리 탐색을 전부 다 하는 방법이다.

그래서 28ms로, 두 번째 방법보다 시간이 오래 걸렸다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
queue<pair<int, int> > Q;
int arr[1001][1001], vis[1001][1001] = {1};

void func() {
    while(!Q.empty()) {
    pair<int, int> cur = Q.front();Q.pop();
        int nx = cur.first;
        int ny = cur.second;//clipboard
        if(nx - 1 > 0 && !vis[nx - 1][ny]) {//삭제
            vis[nx - 1][ny] = vis[nx][ny] + 1;
            Q.push({nx - 1, ny});
        }
        if(nx <= 1000 && !vis[nx][nx]) {//복사
            vis[nx][nx] = vis[nx][ny] + 1;
            Q.push({nx, nx});
        }
        if(nx + ny <= 1000 && !vis[nx + ny][ny]) {//붙여넣기
            vis[nx + ny][ny] = vis[nx][ny] + 1;
            Q.push({nx + ny, ny});
        }
    }
}

int main() {
	int n;
    cin>>n;
    Q.push({1, 0});
    func();
    int ans = 109283471;
    for(int i = 1; i <= 1000; i++) {
        ans = min(ans, vis[n][i]); //최솟값 찾기
    }
    cout<<ans;
}

두 번째 방법이다.

1. 탐색을 하면서 S개의 이모티콘이 만들어졌는지 확인한다.

2. S개의 이모티콘이 만들어졌다면 바로 출력하고 종료한다.

가중치가 1로 동일한 bfs이기에,

S개의 이모티콘이 처음 만들어진 시점이 최단시간이라는 것이 보장된다.

코드도 더 깔끔하고, 4ms로 빠른 풀이이다.

void func() {
    while(!Q.empty()) {
    pair<int, int> cur = Q.front();Q.pop();
        int nx = cur.first;
        int ny = cur.second;//clipboard
        if(nx == n) { //S개의 이모티콘 찾으면 바로 출력
            cout<<vis[nx][ny];
            return;
        }
        if(nx - 1 > 0 && !vis[nx - 1][ny]) { //삭제
            vis[nx - 1][ny] = vis[nx][ny] + 1;
            Q.push({nx - 1, ny});
        }
        if(nx <= 1000 && !vis[nx][nx]) { //복사
            vis[nx][nx] = vis[nx][ny] + 1;
            Q.push({nx, nx});
        }
        if(nx + ny <= 1000 && !vis[nx + ny][ny]) { //붙여넣기
            vis[nx + ny][ny] = vis[nx][ny] + 1;
            Q.push({nx + ny, ny});
        }
    }
}

int main() {
    cin>>n;
    Q.push({1, 0});
    func();
}

태그는 백트래킹이다.
하지만 내 맥북의 vscode에서 pair 기능이 작동하지 않아서 pair를 사용하지 않고 풀었다.
메모리 제한이 작으며, 8자리 수까지 판별하는 문제라 에라토스테네스의 체를 사용할 수는 없다.

내가 푼 방법이다.

0. 한 자리 소수는 2, 3, 5, 7 뿐이다.
=> 큐에 2, 3, 5, 7을 넣어준다.

1. 큐에 담긴 n자리 소수의 뒷자리에 1,3,7,9를 넣어서 n + 1자리의 숫자를 만든다.

1 ~ 3의 과정을 n - 1번 반복하면 n자리 수의 소수만 큐에 남는다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int dx[4] = {1,3,7, 9};
int n, ans;
queue <int> Q;

void Prime() {
    int size = Q.size();
    while(size--){
        for(int i = 0; i < 4; i++) {
            bool isPrime = 1;
            int cur = Q.front() * 10 + dx[i];

            for(int j = 3; j <= sqrt(cur); j++) {
                if(cur % j == 0){ 
                isPrime = 0;
                break;
                }
            }
            if(isPrime) {
                Q.push(cur);
            }
        }
        Q.pop();
    }
}

int main() {
    Q.push(2);
    Q.push(3);
    Q.push(5);
    Q.push(7);
    cin>>n;

    for(int i = 1; i < n; i++) {
        Prime();
    }
    
    ans = Q.size();
    for(int i = 0; i < ans; i++) {
        cout<<Q.front()<<'\n';
        Q.pop();
    }
}