경우없는 개발 블로그

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

#문제 간단 정리

#문제 해결 방법

간단한 문자열 파싱 구현문제

주요 요구하는 구현 조건은 연속된 X 를 판별하는데 있다.

나는 연속된 x를 추적하는 seq 변수를 만들어서

 '.' 이 나온다면 초기화를 시켯다

여기서 seq 을 결과값 nums 이중벡터에 담는데

0이라면 담기지 않게 해두었다

그리고 나중에 비어있는 벡터에는 0을 출력하게 했다

#전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    

    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        vector<vector<char>> nng(n);

        for (int i = 0; i < n; i++) {
            string s; cin >> s;
            for (int j = 0; j < n; j++) {    
                 nng[i].push_back( s[j]);
            }
        }

        vector<vector<int>> nums(2*n);

        //열 탐색
        for (int i = 0; i < n; i++) {
            int seq = 0;
            for (int j = 0; j < n; j++) {
                if (nng[i][j] == 'X') seq++;
                else {
                    if (seq != 0) {
                        nums[i].push_back(seq);
                        seq = 0;
                    }
                }
            }
            if (seq != 0) {
                nums[i].push_back(seq);
            }
        }

        //행탐색
        for (int i = 0; i < n; i++) {
            int seq = 0;
            for (int j = 0; j < n; j++) {
                if (nng[j][i] == 'X') seq++;
                else {
                    if (seq != 0) {
                        nums[n+i].push_back(seq);
                        seq = 0;
                    }
                }
            }
            if (seq != 0) {
                nums[n+i].push_back(seq);
            }
        }

        // 출력: 행 결과 먼저
        for (int i = 0; i < n; i++) {
            if (nums[i].empty()) cout << "0";
            else {
                for (auto a : nums[i]) {
                    cout << a << ' ';
                }
            }
            cout << '\n';
        }

        // 출력: 열 결과 나중에
        for (int i = 0; i < n; i++) {
            if (nums[n + i].empty()) cout << "0";
            else {
                for (auto a : nums[n + i]) {
                    cout << a << ' ';
                }
            }
            cout << '\n';
        }

    }
   
    

    return 0;
}

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

#문제 간단 정리

문제 그대로 구현하기

#문제 해결 방법

유행점수 L 이 주어지고 이거보다 저항 R 이 낮은 소들은

유행에 참여하게 되고 유행점수를 K만큼 늘리게 된다

소들이 어느정도 유행에 참여한는지를 출력하는 문제다

#전체 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;

int main() {
    
    int N, L, K;
    cin >> N >> L >> K;

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


    bool flag = true;
    int cows = 0;
    while (flag == true) {
        flag = false;
        for (int i = 0; i < r.size(); i++) {
            if (L >= r[i]) {
                L += K;
                cows++;
                r.erase(r.begin() + i);
                flag = true;
            }
        }
    }

    cout << cows << '\n';
}

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

#문제 간단 정리

수학문제

#문제 해결 방법

대략 n보다 작은 수의 개수 * n을 포함한 n보다 큰 원소들  + n보다 큰 원소들

구간 만드는 규칙을 잘 살피면 되는데

n보다 작은 원소들을 n을 포함한 원소들과 짝을 만들고

n은 n보다 큰 원소들과 짝을 지어준다고 생각하자

#전체 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;

int main() {
    
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    nums.push_back(0);
    sort(nums.begin(), nums.end());


    int a; cin >> a;

    int down, up;
    bool upflag = false;
    for (int k : nums) {
        if (k < a) {
            down = k;
        }
        if (upflag == false && k > a) {
            up = k;
            upflag = true;
        }
        if (k == a) {
            cout << 0 << '\n';
            return 0;
        }
    }
    //cout << "down :" << down << '\n';
    //cout << "up : " << up << '\n';
    
    int c1 = 0;
    int c2 = 0;
    for (int i = down+1; i <= a-1; i++) {
        c1++;
    }
    for (int i = a; i <= up-1; i++) {
        c2++;
    }

    cout << c1 * c2 + (c2 - 1) << '\n';
}

https://codeforces.com/problemset/problem/1995/A

#전체 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;
 
int main() {
    
    int t;
    cin >> t;
 
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> diagonals(n + 1, 2);
        diagonals[n] = 1;
 
        int placeCount = 0;
 
        while (k > 0) {
            for (int i = k; i > 0; i--) {
                if (i <= n && diagonals[i] > 0) {
                    k -= i;
                    diagonals[i]--;
                    placeCount++;
                    //cout << "k:" << k << '\n';
                    if (k == 0) {
                        break;
                    }
                    break;
                }
            }
        }
 
        cout << placeCount << '\n';
 
    }
 
 
 
}

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

#문제 간단 정리

슬라이딩 윈도우/ 투포인터

#문제 해결 방법

중요한건 a의 개수만큼 윈도우를 만들어서

윈도우 안에 담긴 b 만큼 교체를 해주는 숫자가 최소가 되는 때를 찾는 것이다.

a의 개수만큼의 윈도우를 찾는다는 발상이 조금 어려울 수도 있을 것 같다.

#전체 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;

int main() {
    
    string s;
    cin >> s;

    int n = s.length();
    int aCount = 0;
    int bCount = 0;
    int minBCount = INT_MAX;
    for (char c : s) {
        if (c == 'a') {
            aCount++;
        }
    }
    
    s += s;

    for (int i = 0; i < n; i++) {
        int j =i + aCount-1;

        for (int k = i; k <= j; k++) {
            if (s[k] == 'b') {
                bCount++;
            }
        }
        minBCount = min(bCount, minBCount);
        bCount = 0;
    }

    cout << minBCount << '\n';


}

#문제 해결 방법

가장 중요한 생각은

S ->T로 가는건 가지수가 많기 때문에

시간초과가 나기 매우매우 쉽다는것이다.

혹시 하더라도 일치하는지 확인하는 조건때문에 kmp 가 필요할지도 모르겟다.

때문에 T->S 로 가는 것은 매우 가지수가 적다.

왜냐면 뒤에 A가 있다면 A를 추가한것이기 때문에 빼주고

B가 잇다면 B를 뒤집고 추가해준거라 빼고 뒤집어 주면된다

이 힌트를 알 수 있는것은

바로 추가하는 방향이 한쪽으로만 이뤄진다는 것이다.

만약 양방향으로 추가가 되었다면 불가능했을 것이다.

#전체 코드

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;





int main() {
    string s,t;
    cin >> s >> t;



    while (true) {

        if (t[t.length() - 1] == 'A') {
            t.pop_back();
        }
        else {
            t.pop_back();
            reverse(t.begin(), t.end());
        }

        if (t.length() == s.length()) {
            if (s == t) {
                cout << 1 << '\n';
            }
            else {
                cout << 0 << '\n';
            }
            break;
        }
    }


    return 0;
}

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

#문제 해결 방법

우선 재일 달디달고를 입력하는데는 8회가 걸린다.

그 이후에 달디달고를 연속해서 입력했을때

4개를 만들어야 된다면 2개를 만들고 2개를 복사 할 수 잇다.

8개를 만들어야 된다면 4개를 만들고 복사할 수 있다.

즉 남은 달디달고가 현재 만든 달디달고 의 배수보다 많이 남았다면 

1초가 걸리게 된다.

마지막의 달디단은 +1초로 결정해 주면 된다.

왜냐하면 daldida 까지 2의 배수를 복사해오면서 같이 복사해오면 되기 때문이다

그이후에 n 붙이는데 +1초로 이걸 만들어 주면 된다.

#전체 코드

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



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

    int count = 0;
    if (n == 1) {
        count = 10;
    }
    else if (n == 2) {
        count = 11;
    }
    else if (n >= 3) {
        int temp = 1;
        while (temp <= n) {
            if (temp * 2 <= n) {
                temp *= 2;
                count++;
            }
            else{
                count += 2;
                break;
            }
        }
        count += 8;
    }

    cout << count << '\n';
    return 0;
}

#문제 간단 정리

prefix 와 subfix 가 존재하고

prefix 는 x 까지 이전의 값들끼리 더했을때 최대가 되는 인덱스

subfix 는 y 이후 값들끼리 더했을 떄 최대가 되는 인덱스

y<x 로 주어진다

n길이의 배열로 n x y를 만족하는

배열을 구하라(반드시 존재함)

#문제 해결 방법

우선 x<y 기 때문에

x와 y 사이에는 무조건 1로 채워주는 게 배열을 만들기 가장 쉽다.

왜냐면 가운데는 두 서브픽스와 프리픽스 전부다 영향을 주기 때문이다.

그래서 x 이후에는 감소해야 prefix 가 고정되기 때문에

변갈아서 -1 로 바꿔주고

y 이전에도 번갈아서 -1로 바꿔준다

번갈아서 -1을 해주지 않을 경우에는 반례가 존재하기에 

번갈아서 바꿔줘야한다.

12 7 6 같은 경우가 존재 할 수 있다. (번갈아서 안바꾸면)

#전체 코드

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


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

    while (t--) {
        int n, x, y;
        cin >> n >> x >> y;
        vector<int> a(n, 1);

        // x 이후의 1의 개수보다 -1의 개수가 많아야 한다
        for (int i = x; i < n; i += 2) {
            a[i] = -1;
        }

        // y 이전의 1의 개수보다 -1의 개수가 많아야 한다
        for (int i = y-2; i >=0; i -= 2) {
            a[i] = -1;
        }


        for (int i = 0; i < n; ++i) {
            cout << a[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

#문제 간단 정리

mx는 처음에 0으로 주어진다

배열에서 고르면 그 고른 값으로 mx 가 결정되고

상대방에 턴에는 mx 이상인 값만 고를 수 있다.

alice 가 이길 수 있는지 없는지 리턴하라는 문제

#문제 해결 방법

요지는 모든 숫자를 카운팅 소트를 해준 다음에

모두가 짝수로 존재한다면 패배하고

홀수개수가 존재한다면 승리한다

왜냐하면 일단 가장 높은 숫자의 개수가 짝수개라면

먼저 선택하지 않고 

홀수 개수를 먼저 선택하면 이길 수 있기 때문

5

3 3 3 4 4

일때 3 을 먼저 선택하면 이길 수 있다

만약 가장 높은 숫자가 홀수개라면 그냥 이길 수 있다

6

3 3 3 4 4 4

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
 
    while (t--) {
 
        //첫턴에 mx를 설정 가능하고, 모든 값들이 mx 이하라면 승리
        //현재 가장 높은게 홀수개라면 승리 짝수개라면 패배
 
        int n;
        cin >> n;
 
        vector<int> counting(10002, 0);
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
 
        for (auto i : a) {
            counting[i]++;
        }
 
        vector<int> compress;
 
        for (int i = 10001; i > 0; i--) {
            if (counting[i] != 0) {
                compress.push_back(counting[i]);
            }
        }
 
        bool win = false;
        for (auto i : compress) {
            if (i % 2 == 0) {
            }
            else {
                win = true;
            }
        }
 
 
        if (win) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
 
    return 0;
}

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

#문제 간단 정리

시뮬레이션 문제..

천천히 구현을 하자

#문제 해결 방법

1.종수가 움직임

    -> 만약 움직일 위치에 로봇이있다면 이동횟수 출력하고 종료

2. 로봇이 움직임

    -> 8개의 방향에 대해서 가장 종수랑 가까워 지는 방향을 계산

    -> 2차원배열에 로봇들의 개수를 입력

    ->2개이상이면  '.'으로 1개라면 'R'로 맵에 입력 0개라면 로봇이 없으니 '.'로 입력

#전체 코드

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

int dx[9] = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };
int dy[9] = { 1, 1, 1, 0, 0, 0, -1, -1, -1 };

vector<vector<char>> world;
pair<int, int> jong;
vector<pair<int, int>> robots;
int r, c;
int moveCount;

bool boundary(int y, int x) {
    return (0 <= y && y < r && 0 <= x && x < c);
}

bool moveJong(int input) {
    int ny = jong.first + dy[input];
    int nx = jong.second + dx[input];

    if (world[ny][nx] == 'R') {
        cout << "kraj " << moveCount + 1 << '\n';
        return false;
    }
    else {
        world[jong.first][jong.second] = '.';
        jong = { ny, nx };
        world[ny][nx] = 'I';
        moveCount++;
        return true;
    }
}

void moveRobot() {
    vector<vector<int>> newPos(r, vector<int>(c, 0));
    vector<pair<int, int>> newRobots;

    for (auto& robot : robots) {
        int minDist = 1e9;
        int bestY = robot.first, bestX = robot.second;

        for (int i = 0; i < 9; i++) {
            int ny = robot.first + dy[i];
            int nx = robot.second + dx[i];
            if (boundary(ny, nx)) {
                int dist = abs(ny - jong.first) + abs(nx - jong.second);
                if (dist < minDist) {
                    minDist = dist;
                    bestY = ny;
                    bestX = nx;
                }
            }
        }

        if (world[bestY][bestX] == 'I') {
            cout << "kraj " << moveCount << '\n';
            exit(0);
        }
        newPos[bestY][bestX]++;
        newRobots.push_back({ bestY, bestX });
    }

    robots.clear();
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (newPos[i][j] == 1) {
                robots.push_back({ i, j });
                world[i][j] = 'R';
            }
            else if (newPos[i][j] > 1) {
                world[i][j] = '.';
            }
            else if (newPos[i][j] == 0) {
                world[i][j] = '.';
            }
        }
    }
    world[jong.first][jong.second] = 'I';
}

int main() {
    cin >> r >> c;
    world.resize(r, vector<char>(c));

    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            world[i][j] = s[j];
            if (s[j] == 'I') {
                jong = { i, j };
            }
            else if (s[j] == 'R') {
                robots.push_back({ i, j });
            }
        }
    }

    string command;
    cin >> command;
    moveCount = 0;

    for (char cmd : command) {
        if (!moveJong(cmd - '1')) {
            return 0;
        }
        moveRobot();
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cout << world[i][j];
        }
        cout << '\n';
    }

    return 0;
}