경우없는 개발 블로그

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

#문제 간단 정리

2학년과 1학년이 섞인 줄에서

가장 앞에있는 2학년과 1학년을 

하나씩 없에는 기능을 구현하는

구현 + 시뮬레이션 문제

#문제 해결 방법

우선 나이브하게 

그냥 1학년과 2학년을 k만큼 탐색해서

벡터에서 제거해주는 나이브한 로직을 생각 해 낼 수 있는데

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {

    int n, k;
    cin >> n >> k;

    vector<int> line(n);

    for (int i = 0; i <n; i++) {
        cin >> line[i];
    }

    int time = 0;
    
    while (!line.empty()) {
        bool grade1 = false;
        bool grade2 = false;
        int grade1Index = 0;
        int grade2Index = 0;

        int checkLength = line.size();
        checkLength = min(k, checkLength);

        for (int i = 0; i < checkLength; i++) {
            if (line[i] == 1 && grade1 == false) {
                grade1Index = i;
                grade1 = true;
            }
            if (line[i] == 2 && grade2 == false) {
                grade2Index = i;
                grade2 = true;
            }

        }
        if (grade1 && grade2) {
            if (grade1Index < grade2Index) {
                line.erase(line.begin() + grade2Index);
                line.erase(line.begin() + grade1Index);
            }
            else {
                line.erase(line.begin() + grade1Index);
                line.erase(line.begin() + grade2Index);
            }
        }
        else if (grade2) {
            line.erase(line.begin() + grade2Index);
        }
        else if (grade1) {
            line.erase(line.begin() + grade1Index);
        }
           
;
        time++;
    }

    cout << time << '\n';

    return 0;
}

벡터에서 제거하는 부분에서도 시간초과가 날 수 있지만

그전에 간단하게 만약 k = n 이라고 하게 되면 

항상 n개를 탐색하게 되어서 매우 시간복잡도 가 크게 된다

때문에 나는

1학년과 2학년의 위치를

덱에 넣고

얼마만큼 빠져나간지 알도록 인덱스를 사용하였다

현재 줄에서 빠져나간 만큼 인덱스를 올려서 인덱스를 참조하도록 하였다.

여기서 1학년 덱과 2학년 덱을 조사해서 맨 앞에 있는 값이 

인덱스 + k 의 값 이하의 값을 가지고 있다면 

덱에서  pop 해주고 인덱스를 올려 줬다.

이렇게 남은 1학년과 2학년의 숫자와

줄의 길이를 빠르게 추적 가능하다

정확히 이런 기능을 어떻게 구현할지 물어보는 문제라고 볼 수 있겠다.

아 물론 덱을 안쓰고 벡터를 역순으로 집어 넣는다던가 하는 식으로 덱을 안써도 할 수 있겟지만

직관적으로 풀려고 덱을 사용하였다.

#전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <deque>;

using namespace std;

int main() {

    int n, k;
    cin >> n >> k;

    deque<int> line(n);
    deque<int> grade1;
    deque<int> grade2;
    int lineSize = line.size();

    for (int i = 0; i < n; i++) {
        cin >> line[i];
 
        if (line[i] == 1) {
            grade1.push_back(i);
        }
        else {
            grade2.push_back(i);
        }
    }


    int time = 0;
    int index = 0;

    while (index < line.size()) {


        //남은 인덱스 확인
        int checkLength = index + k - 1;
        checkLength = min(lineSize -1 , checkLength);

        if (!grade1.empty() && grade1.front() <= checkLength) {
            index++;
            grade1.pop_front();
        }
        if (!grade2.empty() && grade2.front() <= checkLength) {
            index++;
            grade2.pop_front();
        }

        time++;
    }

    cout << time << '\n';

    return 0;
}

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

#문제 간단 정리

N 이 주어지고 

N 이하의 숫자들에서

각 자리수를 곱햇을때 가장 커지는 숫자를 찾는 문제

#문제 해결 방법

N 이하의 숫자들의 자리수의 곱의 최대라는 말은

4876이면 4 *  8 * 7 * 6  이렇게 곱할 수 있고

4876 이하의 숫자인 3999도

곱해서 3 * 9 * 9 * 9 를 곱해서 최대값을 찾을 수 있다.

여기서 쉽게 생각 할 수 있는건 9를 최대한 많이 만든다는건데

일단 어떤 자리수를 1내리면 그 뒤에 숫자들은 전부 9로 만들수 있다.

때문에 각 자리수를 한번씩 1 내리고 그 뒤에수를 전부 9로 만들어 주면서

 최대값을 찾아주면 된다.

#전체 코드

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

typedef long long ll;

int main() {



    string s;
    cin >> s;

    ll startMax = 1;

    for (int i = 0; i < s.length(); i++) {
        
        if (s[i] - '0' != 0) {
            startMax *= s[i] - '0';
        }
    }



    for (int i = 0; i < s.length(); i++) {

        ll tempMax = 1;
        if (s[i] - '0' - 1 != 0) { //1 내려서 0이면 곱하지 않고 넘어감
            tempMax *= s[i] - '0' - 1;
        }

        for (int j = i + 1; j < s.length(); j++) { //이후 자리수들 전부 9로 만들기

            tempMax *= 9;

        }

        for (int t = 0; t < i; t++) { //이전자리수들 곱해주기
            if(s[t] - '0' != 0)
                tempMax *= s[t] - '0';

        }

        startMax = max(tempMax, startMax);
    }

    cout << startMax << '\n';

    return 0;
}

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

#문제 간단 정리

이 문제는 동시에 빙고가 나오는지 확인을 하면 되는데

빙고는 행 빙고만 취급한다.

#문제 해결 방법

만약 두 빙고카드에 같은 행에

같은 숫자가 존재한다면 

비길 수 있는 가능성으로 만드는 가능성이 존재한다.

하지만 만약

1 2 3 4 5

1 6 7 8 9

2 3 4 6 7

1 2 3 4 5

에서 1을 찾고

1 6 7 8 9 

에서 1을 찾아서

비긴다고 생각을해도

나머지 2 3 4 5, 6 7 8 9

을 빙고하다보면

2 3 4 6 7 행이 빙고가 되서 비기지 않는다

즉 다른카드에서 겹치는 쌍을 찾고

1 2 3 4 5 에서 1을 골랏다면 2 3 4 5 를 추출

1 6 7 8 9 에서 1을 골랏다면 6 7 8 9 를 추출해서

2 3 4 5 6 7 8 9 로 이루어진 빙고가 없는지 조사해야된다.

#전체 코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<vector<vector<int>>> numbers;
int n;

//각 행이 나머지 숫자들로 빙고가 되는지 학인하기 , 빙고가 안된다면 false 된다면 true
bool remainMatch(vector<int>& remainOne, vector<int>& remainTwo, int dupi1, int dupj1, int dupi2, int dupj2) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < 5; j++) {
            //같은세트의 같은 행은 조사하지 않음
            if (i != dupi1 || j != dupj1) {
 
                if (i != dupi2 || j != dupj2) {


                    vector<bool> check(5, false);

                    for (int k = 0; k < 5; k++) {

                        for (auto a : remainOne) {
                            if (numbers[i][j][k] == a) {
                                check[k] = true;

                            }
                        }
                        for (auto a : remainTwo) {
                            if (numbers[i][j][k] == a) {
                                check[k] = true;
                            }
                        }

                    }

                    bool allCheck = true;
                    for (auto a : check) {
                        if (!a) {
                            allCheck = false;
                        }
                    }
                    //전부 true 면 false 반환

                    if (allCheck) {

                        return true;
                    }

                }
            }

        }


    }

    return false;
}

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) {
        vector<vector<int>> temp(5, vector<int>(5));
        for (int u = 0; u < 5; u++) {
            for (int j = 0; j < 5; j++) {
                cin >> temp[u][j];
            }
        }

        numbers.push_back(temp);
    }

    //일치되는 숫자를 찾고 , 일치되는 숫자 쌍의 행에서 나머지를 추출해서 그 나머지들로 이뤄지는 빙고가 있는지 확인
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < 5; k++) {
            for (int t = 0; t < 5; t++) {
                int target = numbers[i][k][t];

                vector<int> remainOne;

                for (int b = 0; b < 5; b++) {
                    if (b == t) continue;
                    //추출한 첫번쨰 숫자의 나머지 행의 원소들 저장
                    remainOne.push_back(numbers[i][k][b]);
                }

                //다음 빙고셋트들 확인
                for (int j = i + 1; j < n; j++) {

                    for (int p = 0; p < 5; p++) {
                        for (int l = 0; l < 5; l++) {
                            if (target == numbers[j][p][l]) { //같으면 나머지 챙겨서 확인

                                vector<int> remainTwo;

                                for (int b = 0; b < 5; b++) {
                                    if (b == l) continue;
                                    //일치한 두번째 숫자의 나머지 행의 원소들 저장
                                    remainTwo.push_back(numbers[j][p][b]);
                                }


                                if (!remainMatch(remainOne, remainTwo, i, k, j, p)) {
                                    cout << i + 1 << ' ' << j + 1 << '\n';
                                    return 0;
                                }


                            }
                        }
                    }

                }

            }
        }
    }

    cout << "no ties" << '\n';
    return 0;
}

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

#문제 간단 정리

#문제 해결 방법

    // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 

일단 해결로직은 저렇긴한데

dp를 떠올리는 발상을 정리해보자면 

일단 특정 숫자를 쓰냐 안쓰냐로 생각 할 수 있고

j를 안쓰고 만들면 j-1 개를 가지고 만드는 가지수와 같고

j까지의 숫자를 써서 N을 만드는 방법은 = j-1 까지의 숫자를  써서 N-j 을 만들는 방법 + j를 안쓰고 만드는 방법으로 나눌수 있다

때문에 i 를 j 개의 숫자를 써서 만드는

dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수 를 떠올리면 된다

#전체 코드

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
#define MOD 100999

int dp[2001][2001];

int main() {

    int t;
    int n;

    // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 


    dp[0][0] = 1;
    for (int i = 1; i < 2001; i++) {
        dp[i][0] = 0;
        dp[0][i] = 1;
    }
    for (int i = 1; i < 2001; i++) {
        for (int j = 1; j < 2001; j++) {
            dp[i][j] = dp[i][j - 1];  //j를 포함하지 않고 i를 만드는 경우
            if (i >= j) {
                dp[i][j] += dp[i - j][j - 1];
                dp[i][j] %= MOD;
            }
        }
    }

    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n][n] << endl;
    }


    return 0;
}

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

#문제 간단 정리

#문제 해결 방법

맵을 쓰는 간단한 문제

eof와 

자리수 출력에 주의하자

#전체 코드

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

using namespace std;

int main() {
    map<string, int> trees;
    int total = 0;
    string tree;

    while (getline(cin, tree)) {
        trees[tree]++;
        total++;
    }


    cout << fixed << setprecision(4);
    for (auto& entry : trees) {
        double percentage = (entry.second * 100.0) / total;
        cout << entry.first << " " << percentage << '\n';
    }

    return 0;
}

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

#문제 간단 정리

#문제 해결 방법

우선 동적 계획법을 사용해야된다는건 쉽게 알아차릴 수 있다

왜냐면 

1. 중복되는 부분 문제(Overlapping Subproblems)

2. 최적 부분 구조(Optimal Substructure)

를 n의 조합을 알기 위해서는 이전의 수가 필요하고 이전의 수 조합으로 구할 수 있다는 것을 쉽게 알 수 있기 때문이다.

그렇다면 선택할수 있는건 

그 수의 조합을 만들기 위해 어떤수를 사용하던가 사용하지 않던가 

로 나뉜다는 것을 알 수 있다.

   // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 

#전체 코드

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
#define MOD 100999

int dp[2001][2001];

int main() {

    int t;
    int n;

    // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수
    // 1. j를 포함하지 않고 만드는경우
    // dp[i][j-1];
    // 2. j를 포함해서 i를 만드는경우
    // if(i>=j)  D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; 
    // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 


    dp[0][0] = 1;
    for (int i = 1; i < 2001; i++) {
        dp[i][0] = 0;
        dp[0][i] = 1;
    }
    for (int i = 1; i < 2001; i++) {
        for (int j = 1; j < 2001; j++) {
            dp[i][j] = dp[i][j - 1];  //j를 포함하지 않고 i를 만드는 경우
            if (i >= j) {
                dp[i][j] += dp[i - j][j - 1];
                dp[i][j] %= MOD;
            }
        }
    }

    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n][n] << endl;
    }


    return 0;
}

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

#문제 간단 정리

기본적인 bfs 구현문제

#문제 해결 방법

bfs 를 조회할때 

색약인지 색약인지 아닌지를 구분받아서 조회할 수 있는지 

물어보는 문제이다

색약인경우의 조건을 잘 구현하자

#전체 코드

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

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

int n;
vector<vector<char>> rgb;
vector<vector<bool>> check;
int blindCount;
int nBlindCount;

void bfs(int y, int x, bool blind) {

    queue<pair<int, int>> q;
    q.push({ y,x });
    check[y][x] = true;

    char color = rgb[y][x];


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

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (0<=nx && nx <n && 0<= ny && ny<n ) {

                if (check[ny][nx] == false) {
                    if (rgb[ny][nx] == color) {
                        q.push({ ny, nx });

                        check[ny][nx] = true;
                    }
                }


            }

        }

    }

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

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < n) {

                if (check[ny][nx] == false) {
                    if (color == 'B' && rgb[ny][nx] == color) {
                        q.push({ ny, nx });

                        check[ny][nx] = true;
                    }
                    else if (color == 'R' || color == 'G') {
                        if (rgb[ny][nx] == 'R' || rgb[ny][nx] == 'G') {
                            q.push({ ny, nx });

                            check[ny][nx] = true;
                        }

                    }
                }



            }

        }

    }


}

int main() {
    cin >> n;

    rgb.resize(n, vector<char>(n));
    check.resize(n, vector<bool>(n, false));

    for (int i = 0; i < n; i++) {
        string s; cin >> s;

        for (int j = 0; j < n; j++) {
            rgb[i][j] = s[j];

        }

    }

    blindCount = 0;
    nBlindCount = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == false) {
                bfs(i, j, false);
                nBlindCount++;
            }

        }
    }

    check.assign(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == false) {
                bfs(i, j, true);
                blindCount++;
            }


            
        }
    }

    cout << nBlindCount << ' ' << blindCount << '\n';

    return 0;
}

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

#문제 간단 정리

bfs를 통한 거리 문제

#문제 해결 방법

이 문제는 bfs를 통해서

가장 먼 거리의 위치 를 찾는 문제이다

전형적이 bfs에서 조금 활용이라고 볼 수 있다.

모든 육지 노드에 대해 돌면서 그 육지에서

가장 먼 노드를 찾고

가장 먼 거리를 변수에 저장하면 된다.

#전체 코드

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

using namespace std;

int n, m;

int dy[4] = { 0,1,0,-1 };
int dx[4] = { -1,0,1,0 };
vector<vector<char>> tMap;
int maxDist;

int bfs(int inputY, int inputX) {
    //좌표,거리
    queue<pair<int, int>> q;
    vector<vector<int>> dist(n, vector<int>(m, -1));

    q.push({ inputY,inputX });
    dist[inputY][inputX] = 0;
    int mdist = 0;

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

        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < m && 0 <= ny && ny < n) {
                if (tMap[ny][nx] == 'L') {
                    if (dist[ny][nx] == -1 || dist[ny][nx] > dist[y][x] + 1) {
                        q.push({ ny,nx });
                        dist[ny][nx] = dist[y][x] + 1;
                    }
                }
            }
        }

    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            mdist = max(mdist, dist[i][j]);
        }
    }

 /*   for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }

    cout << '\n';*/
    return mdist;
}

int main()
{

    cin >> n >> m;

    tMap.resize(n, vector<char>(m));
    maxDist = 0;

    for (int i = 0; i < n; i++) {
        string input;
        cin >> input;

        for (int j = 0; j < m; j++) {
            tMap[i][j] = input[j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tMap[i][j] == 'L') {
                maxDist = max(bfs(i, j), maxDist);
            }
        }
    }

    cout << maxDist << '\n';

}

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

#문제 간단 정리

그래프 탐색을 하면 된다

#문제 해결 방법

dfs로 풀었는데

트리의 부모만 확인해 주면 되니까 이렇게 복잡하게 풀 필요는 없어보인다..

그래서 실버1인듯하다

#전체 코드

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <climits>

using namespace std;

map<string, vector<string>> node;
map<string, bool> dfsCheck;
int result;

void dfs(string start, string target) {

    if (start == target) {
        result = 1;
        return;
    }



    for (auto a : node[start]) {
        if (!dfsCheck[a]) {
            dfsCheck[start] = true;
            dfs(a, target);
            dfsCheck[start] = false;
        }
    }

    
}

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

    for (int i = 0; i < n - 1; i++) {
        string s1, s2;
        cin >> s1 >> s2;

        dfsCheck[s1] = false;
        dfsCheck[s2] = false;

        node[s1].push_back(s2);
    }

    string a1, a2;
    cin >> a1 >> a2;
    result = 0;

    dfs(a1, a2);
    dfs(a2, a1);
    
    cout << result << '\n';

    return 0;
}

#문제 간단 정리

#문제 해결 방법

우선순위 큐를 써도 되지만

n이 작기때문에

나이브하게 그냥 구현해도 돌아간다

#전체 코드

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

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

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

    vector<int> cashier(n, 0);  // 각 계산대의 남은 시간
    vector<int> ans(c);  // 각 고객이 배정된 계산대 번호를 저장

    for (int i = 0; i < c; i++) {
        // 가장 빨리 비는 계산대를 찾기
        int min_time = cashier[0];
        int min_index = 0;

        for (int j = 1; j < n; j++) {
            if (cashier[j] < min_time) {
                min_time = cashier[j];
                min_index = j;
            }
        }

        // 고객을 가장 빨리 비는 계산대에 배치
        ans[i] = min_index + 1;
        cashier[min_index] += times[i];  // 해당 계산대의 남은 시간 갱신
    }

    // 결과 출력
    for (int a : ans) {
        cout << a << " ";
    }

    return 0;
}