재시민

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

문제 개요
이 문제는 우주선이 현재 위치에서 목표 위치로 이동할 때, 주어진 규칙에 따라 최소한의 이동 횟수를 구하는 문제이다. 이동하는 규칙은 다음과 같다:

1. 우주선은 매번 이동할 때마다 "최대 속도"가 1만큼 변할 수 있다. 이 최대 속도는 1부터 시작하며, 속도는 양수만 가능하다.
2. 우주선이 목표 위치에 도달하기 전까지 속도를 감소시킬 수 없다. 즉, 우주선이 목표 위치에 도달할 때까지 속도는 증가하거나 일정하게 유지될 수 있다.
3. 목표 위치에 도달한 순간에는 속도가 0이 된다.

입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 정수 (x)와 (y)로 이루어져 있으며, 이는 우주선의 현재 위치와 목표 위치를 나타낸다. (0 ≤ x < y ≤ (2^{31}-1))

출력
각 테스트 케이스에 대해, 목표 위치에 도달하기 위한 최소 이동 횟수를 출력한다.

문제 풀이

이 문제를 풀기 위해서는 특정 패턴을 찾는 것이 중요하다. 먼저, 거리 (d = y - x)를 계산한 뒤, 이 거리에 도달하기 위해 우주선이 취할 수 있는 이동 패턴을 살펴봐야 한다.

1. 거리 분석

우주선이 움직일 수 있는 패턴은 다음과 같다:

• 시작할 때 속도를 1씩 증가시키다가, 일정 속도로 유지한 후, 다시 1씩 감소시키며 목표 위치에 도달한다.
• 증가하는 속도 구간과 감소하는 속도 구간의 대칭성을 고려해야 한다.

2. 움직임 패턴

• 거리 (d)에 대해, 속도를 증가시켜서 움직일 수 있는 최대 거리와 그에 필요한 횟수를 계산한다.
• 그 후, 남은 거리만큼 추가적인 이동이 필요한지 판단한다.

이동 패턴 정리

• (n^2 \leq d < (n+1)^2) 일 때, 이 거리를 최소한의 이동으로 도달할 수 있는 패턴은:
  • (d = n^2) -> 총 2n - 1번 이동
  • (n^2 < d \leq n^2 + n) -> 총 2n번 이동
  • (n^2 + n < d < (n+1)^2) -> 총 2n + 1번 이동

이를 바탕으로 C++ 코드를 작성하였다.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        long long x, y;
        cin >> x >> y;
        long long d = y - x;
        long long n = sqrt(d);

        if (d == n * n) {
            cout << 2 * n - 1 << endl;
        } else if (n * n < d && d <= n * n + n) {
            cout << 2 * n << endl;
        } else {
            cout << 2 * n + 1 << endl;
        }
    }

    return 0;
}

코드 설명

1. 거리 계산: 각 테스트 케이스에 대해 목표 위치와 현재 위치의 거리를 계산한다.
2. 최소 이동 횟수 계산: 주어진 거리 (d)에 대해 최소 이동 횟수를 계산한다. 이때, 거리의 제곱근을 기준으로 3가지 경우로 나누어 결과를 구한다.
   • (d = n^2) 일 경우: 2n - 1번 이동
   • (n^2 < d \leq n^2 + n) 일 경우: 2n번 이동
   • (n^2 + n < d < (n+1)^2) 일 경우: 2n + 1번 이동

결론

이 문제는 수학적 패턴을 분석하는 과정이 중요하다. 각 테스트 케이스에서 목표 위치에 도달하기 위한 최소한의 이동 횟수를 구하기 위해 제곱근과 그 범위에 따른 계산이 핵심이다. 위의 알고리즘을 사용하면 효율적으로 문제를 해결할 수 있다.

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

문제 설명

연속된 k 개의 초밥을 먹으면 1개의 쿠폰을 준다.

이 때, 이벤트를 참여하면서 먹을 수 있는 초밥 개수의 최댓값을 구하자.

인사이트

처음에 생각한 방법

1. 투포인터를 사용하기 위해 deque을 사용하고 left, right를 이용해 슬라이딩 윈도우를 구현하자.
2. 한번의 슬라이딩 윈도우 탐색을 하고나면 deque의 원소를 unorderd_set 에 옮겨 중복되는 값을 제거하고 쿠폰으로 받는 초밥의 번호가 포함되어있는지 확인해 최대 가짓수를 최신화한다.

오류 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
using namespace std;

int N, d, k, c;

vector<int> rail;
unordered_set<int> s;
deque<int>dq;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> d >> k >> c;

    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        rail.push_back(n);
    }

    for (int i = 0; i < k; i++) {
        dq.push_back(rail[i]);
    }

    int left = 0;
    int right = k - 1;

    int maxx = dq.size();
    for (int i = 1; i <= N; i++) {
        dq.pop_front();

        left++;
        right++;

        if (left >= N) {
            left = 0;
        }
        if (right >= N) {
            right = 0;
        }

        dq.push_back(rail[right]);
        //최댓값 최신화

        unordered_set<int> tmp(dq.begin(), dq.end());

        bool is_coupon = false;

        if (tmp.find(c) != tmp.end()) {
            is_coupon = false;
        }
        else {
            is_coupon = true;
        }

        if (maxx <= tmp.size()) {
            maxx = tmp.size();
            if (is_coupon) {
                maxx += 1;
            }
        }
    }
    cout << maxx;
    return 0;
}

하지만 시간초과라는 결과를 얻게 되었다. for 루프를 돌 때마다 새로운 set을 생성하고 탐색하는 과정에서 O(Nk) 의 시간이 걸린다.

수정된 인사이트

1. deque 을 이용한 윈도우
   -> unordered_map 을 사용
2. unodered_set 을 사용한 중복제거
   -> unordered_map에서 key(초밥번호) 에 해당하는 value 값의 조정을 통해 중복이면 1 초과인지 확인을 해 체크

정답코드

#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>
using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, d, k, c;
    cin >> N >> d >> k >> c;

    vector<int> rail(N);
    for (int i = 0; i < N; i++) {
        cin >> rail[i];
    }

    unordered_map<int, int> sushi_count;
    int total_types = 0; // 현재 윈도우 내의 초밥 종류 수
    int max_types = 0;

    // 초기 윈도우 설정
    for (int i = 0; i < k; i++) {
        if (sushi_count[rail[i]]++ == 0) total_types++;
    }
    // 쿠폰 초밥 추가
    if (sushi_count[c]++ == 0) total_types++;

    max_types = total_types;

    // 슬라이딩 윈도우
    for (int i = 1; i < N; i++) {
        // 앞에서 초밥 제거
        if (--sushi_count[rail[i-1]] == 0) total_types--;

        // 뒤에 새로운 초밥 추가
        int new_sushi = rail[(i + k - 1) % N];
        if (sushi_count[new_sushi]++ == 0) total_types++;

        // 쿠폰 초밥 확인
        max_types = max(max_types, total_types + (sushi_count[c] == 0));
    }

    cout << max_types;

    return 0;
}

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

문제 설명

0으로 이루어진 바다위에 떠있는 1로 이루어진 섬.

섬끼리 다리를 지으려고 하는데 가장 짧은 다리를 구하자.

인사이트

섬들 중 어느 섬이든 간에 가장 짧은 다리를 만드는 경우를 출력하면 된다.

1. 전체 BFS 순회를 통해 몇 개의 섬이 있으며 지도에 있는 1이 몇번째 섬에 부분에 해당하는지 파악
2. 지도를 이중 for loop를 통해 지도 값이 1 인 칸에 대하여 주위 네 개의 면 중 0이 있다면 큐에 넣는다.
   1. 큐에 들어온 좌표를 기준으로 BFS 를 실행
   2. 주위 네 개의 면 중 하나가 0 이면 큐에 push
   3. 주위 네 개의 면 중 하나가 1 이고 다른 섬이면 정답 벡터의 담기
      1. 시작 좌표, 끝 좌표를 이용해 |끝좌표 - 시작좌표| - 1 값을 구해 최소 다리 길이를 구함
3. 이중 for loop 가 끝나면 정답 벡터의 최솟값을 출력

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include<queue>

using namespace std;

int N, M;

int land[101][101];
int land_idx[101][101];
bool visited[101][101];
bool visited_idx[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int> ans;
    cin >> N;
    //초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> land[i][j];
        }
    }

    //2차원 배열을 순회하면서 땅이 몇개인지 파악하고 각 행렬의 1이 속하는 땅의 번호를 기입
    int idx = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited_idx[i][j])continue;
            if (land[i][j] != 1)continue;
            queue<pair<int, int>> q;
            q.push(make_pair(i, j));
            visited_idx[i][j] = true;
            idx++;
            land_idx[i][j] = idx;

            while (!q.empty()) {
                int y = q.front().first;
                int x = q.front().second;

                q.pop();

                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                    if (visited_idx[ny][nx])continue;
                    if (land[ny][nx] == 0)continue;
                    q.push(make_pair(ny, nx));
                    visited_idx[ny][nx] = true;
                    land_idx[ny][nx] = idx;
                }
            }
        }
    }


    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j])continue;
            if (land[i][j] != 1)continue;

            queue<pair<int, int>> q;
            //주변에 0이 있는 1인 시작점 찾아서 큐에 넣기
            bool check = false;
            for (int k = 0; k < 4; k++) {
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                if (land[ny][nx] == 0) {
                    if (land_idx[ny][nx] != land_idx[i][j])
                    {
                        check = true;
                    }
                }
                else {
                    continue;
                }
            }
            //4면 중 하나라도 0이면 큐에 담기
            if (check) {
                q.push(make_pair(i, j));
                visited[i][j] = true;
            } 
            //BFS
            while (!q.empty()) {
                int y = q.front().first;
                int x = q.front().second;

                q.pop();

                bool check = false;
                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                    if (visited[ny][nx]) continue;
                    //4면 중 하나가 0 이면 큐에 푸시
                    if (land[ny][nx] == 0) {
                        if (land_idx[ny][nx] != land_idx[i][j])
                        {
                            q.push(make_pair(ny, nx));
                            visited[ny][nx] = true;
                        }
                    //4면 중 하나가 1이면 정답 벡터에 푸시
                    }else if (land[ny][nx] == 1) {
                        if (land_idx[ny][nx] != land_idx[i][j]) {
                            ans.push_back(abs(ny - i) - 1 + abs(nx - j));
                            break;
                        }
                    }

                }
            }
            //재탐색을 위한 방문 초기화
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(land[i][j] == 0)visited[i][j] = 0;
                }
            }

        }
    }

    cout << *min_element(ans.begin(), ans.end());
}

백만년만에 작성하는 근황. 

골드를 달성했다.

앞으로 리액트 공부와 블록체인 공부를 한달만에 할 예정이다.

가즈아