공부흔적

문제 링크

풀이 )

  가장 큰 수를 두개 뽑아 곱했을때가 다른 두 수를 곱했을 때보다 결과가 크기 때문에 우선 내림차순으로 정렬했다.

  이후 앞에서부터 두 수를 뽑아 곱한다.

  이 때 1과 0은 다른 양수와 곱해지는 경우 곱이 합보다 작아지게 되므로 1부터 예외처리해준다.

  n * 1 < n + 1, n * 0 < n + 0

  음수 2개를 곱하는 경우 양수가 되기 때문에 그 값을 최대로 만들기 위해 절댓값이 큰 끝부터 2개씩 곱하면서 더한다.

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

using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];

    sort(v.begin(), v.end(), greater<int>());
    int ans = 0;

    int i = 0;
    for(; i < n; i+=2){
        if(v[i+1] <= 1)
            break;
        ans += v[i]*v[i+1];
    }
    for(; i < n; ++i){
        if(v[i] < 1)
            break;
        ans += v[i];
    }

    int j = n-1;
    for(; j > i; j-=2)
        ans += v[j]*v[j-1];
    if(i == j)
        ans += v[j];

    cout << ans << '\n';
}

문제 링크

풀이 )

  현재 입력받은 수에 대해서 한 자리씩 숫자를 하나씩 바꿔가면서 BFS를 한다.

  같은 수를 다시 Queue에 넣는 것을 방지하기 위해 visited 배열을 사용하여 방문 여부를 확인하여 방문한 경우 Queue에 넣지 않는다.

  한 자리씩 바꾸는 경우 현재 수 num, 자릿수 digit, 바꾸자하는 수 i를 매개변수로 받아 결과값을 반환하는 make( )를 만들었다. (제곱을 구하는 pow( )에서는 밑을 10으로 고정하여 지수만 입력받아 반환하도록 했다.)

  ex ) 1234에서 10^2의 자리수 2를 7로 바꾼다하면 make(1234, 2, 7)을 호출한다.

         1734바꾸면 되므로

• 10^2보다 큰 자리에 대해선 그대로 두기 위해 num/pow(digit+1)*pow(digit+1)
• 10^2자리에서는 pow(digit)*i
• 10^2이하 자리에서는 num%pow(digit);

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

bool prime[10000];

int pow(int num){
    if(!num)
        return 1;
    return 10*pow(num-1);
}

int make(int num, int digit, int i){
    return (num/pow(digit+1)*10+i)*pow(digit)+num%pow(digit);
}

int main(void){

    for(int i = 1000; i < 10000; ++i){
        prime[i] = true;
        for(int j = 2; j < 100; ++j){
            if(i%j==0){
                prime[i] = false;
                break;
            }
        }
    }

    int t;
    cin >> t;
    int a, b;
    while(t--){
        cin >> a >> b;

        queue<pair<int, int> > q;   // 숫자, 단계
        bool visited[10000] = {false, };
        q.push({a, 0});
        visited[a] = true;
        while(1){
            int tmp = q.front().first;
            int cnt = q.front().second;
            if(tmp == b){
                cout << cnt << '\n';
                break;
            }
            visited[tmp] = true;
            q.pop();

            for(int digit = 0; digit < 4; ++digit){
                for(int i = 0; i < 10; ++i){
                    if(digit == 3 && i == 0)
                        continue;
                    a = make(tmp, digit, i);
                    if(visited[a] || !prime[a])
                        continue;
                    q.push({a, cnt+1});
                }
            }
        }
    }
}

문제 링크

풀이 )

  가장 큰 두 수를 뽑아 곱하는 경우가 가장 큰 결과값이 나오기 때문에 먼저 입력받은 수열에 대해서 내림차순으로 정렬해주었다.

• 앞에서부터 두 수가 모두 1보다 큰 경우에 대해서 두 수를 곱해준다.
• 한자리씩 검사하여 1이 있는 경우 1은 다른 수와 곱했을 때 합이 최대가 될 수 없으므로 따로 분류해 둔다. (1+n > 1*n)
• 음수 두 수를 곱하면 양수가 되므로 절댓값이 큰 뒤에서 부터 두 수를 곱해준다.
• 음수가 홀수인 경우 마지막으로 남은 수를 처리한다.

위의 4가지를 순서대로 구현했다.

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

using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];

    sort(v.begin(), v.end(), greater<int>());
    int ans = 0;
    int idx = 0;

    int i = 0;
    for(; i < n; i+=2){
        if(v[i+1] <= 1)
            break;
        ans += v[i]*v[i+1];
    }
    for(; i < n; ++i){
        if(v[i] < 1)
            break;
        ans += v[i];
    }

    int j = n-1;
    for(; j > i; j-=2)
        ans += v[j]*v[j-1];
    if(i == j)
        ans += v[j];

    cout << ans << '\n';
}

문제 링크

풀이 )

  부모 노드에 대한 정보를 입력 받을 때, 반대로 부모 노드에 대한 자식 노드를 저장했다.

  cnt( )에서는 자식 노드를 타고가면서 리프 노드인 경우(자식 노드의 수가 0) 1을 더해주는 방식으로 총 리프 노드의 수를 구한다.

답이 될 수 있는 경우의 수를 3가지로 나눴다.

• 자르는 노드(이하 cut)가 루트인 경우: 남는 노드가 없으므로 0 출력
• cut의 sibling 노드가 있는 경우: cnt(root) - cnt(cut)
• cut의 sibling 노드가 없는 경우: cnt(root) - cnt(cut) + 1

cut의 sibling 노드가 있는 경우 cut을 자르게 되면 sibling 노드가 남기 때문에 root의 리프 노드 수에서 cut의 리프노드 수를 빼주면 된다.

반면 cut의 sibling 노드가 없는 경우 cut을 자르게 되면 cut의 부모 노드가 리프 노드가 되기 때문에 +1을 해주어야 한다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> childrenOf[50];
int parentOf[50];

int cnt(int node){
    int num = childrenOf[node].size();
    if(num == 0)
        return 1;
    int ret = 0;
    for(int i = 0; i < num; ++i){
        ret += cnt(childrenOf[node][i]);
    }
    return ret;
}

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

    int root;
    for(int i = 0; i < n; ++i){
        int parent;
        cin >> parent;
        if(parent == -1)
            root = i;
        else{
            childrenOf[parent].push_back(i);
            parentOf[i] = parent;
        }
    }
    int cut;
    cin >> cut;

    if(cut == root){
        cout << 0;
        return 0;
    }
    int ans = cnt(root)-cnt(cut);
    if(childrenOf[parentOf[cut]].size() == 1)
        ans++;
    cout << ans << '\n';
}

문제 링크

풀이 )

  빈칸에 해당되는 칸을 blank 벡터에 집어 넣는다.

  이후 빈칸을 한 칸씩 1부터 9까지 가능한 숫자를 check( )를 통해 확인하여 집어 넣는다.

  (9까지 모두 불가능하다면, 해당 경우는 종료)

  가능한 경우가 나오면 바로 출력하고 프로그램을 종료하기 위해 blank가 비었을 때 바로 출력하고 exit(0)을 호출한다.

#include <iostream>
#include <vector>

using namespace std;

int board[9][9];

bool check(int x, int y, int num){
    for(int r = 0; r < 9; ++r){
        if(board[r][y] == num)
            return false;
    }

    for(int c = 0; c < 9; ++c){
        if(board[x][c] == num)
            return false;
    }

    for(int r = x/3*3; r < x/3*3+3; ++r){
        for(int c = y/3*3; c < y/3*3+3; ++c){
            if(board[r][c] == num)
                return false;
        }
    }
    return true;
}

void dfs(vector<int>& blank){
    if(blank.empty()){
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                cout << board[i][j];
                if(j == 8)
                    cout << '\n';
                else
                    cout << ' ';
            }
        }
        exit(0);
    }

    int x = blank.back()/10;
    int y = blank.back()%10;
    blank.pop_back();
    for(int i = 1; i < 10; ++i){
        if(!check(x, y, i))
            continue;
        board[x][y] = i;
        dfs(blank);
        board[x][y] = 0;
    }
    blank.push_back(x*10+y);
}

int main(void){
    vector<int> blank;
    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            cin >> board[i][j];
            if(board[i][j] == 0)
                blank.push_back(i*10+j);
        }
    }

    dfs(blank);
}

문제 링크

풀이 )

  M이 1,000,000 이하이므로 cin으로 입력을 받을 시 cin.tie(null), ios::sync_with_stdio(false) 처리를 해주어야 한다.

  또 각 경우에 대해서 O(n^2)인 경우 시간 초과가 발생하게 되므로 해결하기 위해 DP를 이용했다.

  먼저 dp 배열의 행과 열은 각각 시작, 끝을 의미한다.

  dp 배열의 모든 원소 값을 -1로 초기화 시킨다.

  check( )는 시작 s와 끝 e에 대해서

• dp[s][e]가 갱신된 적이 있다면(dp[s][e] != -1), 즉 팰린드롬 여부가 결정된 경우 바로 결과를 반환한다.
• e == s인 경우 즉 글자 하나인 경우 팰린드롬이므로 dp[s][e]를 갱신하고 true 반환
• e < s 인 경우가 오는 경우는 피호출함수에서 매개변수간 차가 1인 경우 예를 들어 check(1, 2)와 같은 경우 뿐이다.
  함수가 호출되기 위해서는 arr[1]와 arr[2]가 같아야 하기 때문에 길이가 2이고, 두 문자가 같다는 의미이다
  따라서 dp[s][e]를 갱신하고 true 반환
• 양쪽 끝 문자가 다른 경우 팰린드롬이 아니므로 dp[s][e]를 갱신하고 false 반환
• 양쪽 끝 문자가 같은 경우 양쪽에서 한칸씩 당기면서 팰린드롬인지 여부 확인

#include <iostream>

using namespace std;

int arr[2000];
int dp[2000][2000];

bool check(int s, int e){
    if(dp[s][e] != -1)
        return dp[s][e];

    if(e <= s)
        return dp[s][e] = true;

    if(arr[s] != arr[e])
        return dp[s][e] = false;

    return dp[s][e] = check(s+1, e-1);
}

int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m;

    for(int i = 0; i < 2000; ++i)
        for(int j = 0; j < 2000; ++j)
            dp[i][j] = -1;

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> arr[i];

    cin >> m;
    while(m--){
        int s, e;
        cin >> s >> e;
        cout << check(s-1, e-1) << '\n';
    }
    return 0;
}