공부흔적

문제 링크

풀이 )

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

• 앞에서부터 두 수가 모두 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;
}

문제 링크

풀이 )

• puyo( ): 터지는지 여부
• dfs( ): puyo( )에서 연속된 4개의 블록이 있는지 확인하기 위한 재귀함수
• pung( ): 4개 이상의 블록이 붙어있는 경우 같은 종류의 블록을 모두 터뜨림
• fall( ): 블록 아래로 내리기

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> field(12);
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void fall(){
    for(int c = 0; c < 6; ++c){
        for(int r = 11; r > 0; --r){
            while(field[r][c] == '.'){
                int flag = true;
                for(int i = r; i > 0; --i){
                    if(field[i][c] != '.')
                        flag = false;
                    field[i][c] = field[i-1][c];
                }
                if(flag){
                    if(field[0][c] == '.')
                        break;
                }
                field[0][c] = '.';
            }
        }
    }
}

void pung(int x, int y, char c){
    field[x][y] ='.';
    for(int dir = 0; dir < 4; ++dir){
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6)
            continue;
        if(field[nx][ny] == c)
            pung(nx, ny, c);
    }
    return;
}

int dfs(int x, int y, char c, vector<vector<bool> > visited){
    int ret = 1;
    visited[x][y] = true;
    for(int dir = 0; dir < 4; ++dir){
        int nx = x+dx[dir];
        int ny = y+dy[dir];
        if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6 || visited[nx][ny])
            continue;
        if(field[nx][ny] == c)
            ret += dfs(nx, ny, c, visited);
        if(ret >= 4)
            break;
    }
    return ret;
}

bool puyo(){
    bool ret = false;
    vector<vector<bool> > visited(12, vector<bool>(6));
    for(int r = 0; r < 12; ++r){
        for(int c = 0; c < 6; ++c){
            if(field[r][c] == '.' || visited[r][c])
                continue;
            if(dfs(r, c, field[r][c], visited) < 4)
                continue;
            pung(r, c, field[r][c]);
            ret = true;
        }
    }
    return ret;
}

int main(void){
    for(int i = 0; i < 12; ++i)
        cin >> field[i];

    int ans = 0;
    while(1){
        if(!puyo()){
            cout << ans << '\n';
            return 0;
        }
        ans++;
        fall();
    }
}

주의)

• puyo( )에서 dfs( )의 결과가 4가 넘어가면 바로 재귀함수를 호출할 필요없이 터뜨리기 때문에 바로 continue 처리해준다.(안해주면 시간초과)
• 터뜨릴때는 한번에
• 떨어뜨리는 부분에서 실수가 많이 일어나는 편이다.

문제 링크

풀이 )

  입력으로 받은 집과 치킨집을 각각 home, chic vector에 넣어줬다.

  풀고나서 보니 city는 한번도 안썼다.

  이후 길이가 chic vector에서 1개를 시작으로 m개까지의 조합을 만들어 선택된 치킨집을 이용해 sum( )을 호출하여 치킨 거리를 계산한다.

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

using namespace std;

int n, m;
vector<pair<int, int> > chic;
vector<pair<int, int> > home;

int calc(pair<int, int> chic, pair<int, int> home){
    return abs(chic.first-home.first)+abs(chic.second-home.second);
}

int sum(vector<int> picked){
    int hLen = home.size();
    int pLen = picked.size();
    int ret = 0;

    for(int i = 0; i < hLen; ++i){
        int tmp = 1e9;
        for(int j = 0; j < pLen; ++j)
            tmp = min(tmp, calc(home[i], chic[picked[j]]));
        ret += tmp;
    }

    return ret;
}

int dfs(vector<int> picked, int cLen, int pos, int cnt){
    if(cnt == 0)
        return sum(picked);

    int ret = 1e7;
    for(int i = pos; i < cLen; ++i){
        picked.push_back(i);
        ret = min(ret, dfs(picked, cLen, i+1, cnt-1));
        picked.pop_back();
    }
    return ret;
}

int main(void){
    cin >> n >> m;
    vector<vector<int> > city(n, vector<int>(n));

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> city[i][j];
            if(city[i][j] == 2)
                chic.push_back({i, j});
            if(city[i][j] == 1)
                home.push_back({i, j});
        }
    }

    int cLen = chic.size();
    int ans = 1e7;
    for(int i = 1; i <= m; ++i)
        ans = min(ans, dfs(vector<int>(0), cLen, 0, i));
    cout << ans << '\n';
}