2023 KAKAO BLIND RECRUITMENT 해설

KAKAO BLIND RECRUITMENT는 문제의 지문 / 테스트케이스 / 풀이를 비상업적, 비영리적 용도로 게시할 수 있다. 광고가 노출되지 않는 블로그에 문제 풀이를 게시하는 것은 비상업적, 비영리적 용도이다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

2022년 09월 24일 14:00 ~ 09월 24일 19:00동안 테스트가 진행되었습니다.
이 글에 나와있는 문제 제목들은 실제 제목이 없어서, 제가 문제가 요구하는 요점에 맞춰 지은 제목입니다.
질문은 언제나 환영입니다.

 

그... 좀 귀찮아서 마지막 두 문제만 풀었습니다.

UPD - 마지막 두 개만 풀었는데도 통과했네요..

미로 탈출(300점)

• 예상 난이도: 골드 하위
  
• 태그: 그리디

지문 요약

문제

격자 안에서 시작 지점 $S$에서 $E$까지 길이가 $K$인 경로로 움직이는데, 움직일 때마다 상하좌우에 맞게 udlr 알파벳으로 경로에 대응되는 문자열을 만듭니다.

조건을 만족하는 경로 문자열 중 사전순으로 가장 앞선 문자열을 출력하세요. 만약 존재하지 않는다면 "Impossible"을 출력하세요.

제약

격자의 크기는 가로와 세로 모두 $50$ 이하입니다. $K$는 적당히 깁니다. 사실 기억이 안 납니다.

풀이

그리디하게 현재 갈 수 있는 상태에서 d > l > r > u의 우선순위로 움직이면 됩니다.

코드

방향이 많이 헷갈립니다. 주의하세요!

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    int f = k-abs(r-x)-abs(c-y);
    if (abs(r-x)+abs(c-y) > k) return "impossible";
    if (f%2 == 1) return "impossible";
    rep(i,1,k) {
        if (r-x > 0 or (f > 0 and x+1 <= n)) { // d
            if (r-x <= 0) f -= 2;
            answer.push_back('d'), ++x;
        } else if (c-y < 0 or (f > 0 and y-1 >= 1)) { // l
            if (c-y >= 0) f -= 2;
            answer.push_back('l'), --y;
        } else if (c-y > 0) { // r
            answer.push_back('r'), ++y;
        } else if (y+1 <= m and f > 0) {
            f -= 2, answer.push_back('r'), ++y;
        } else if (r-x < 0) { // u
            answer.push_back('u'), --x;
        }  else if (x-1 >= 1 and f > 0) {
            f -= 2, answer.push_back('u'), --x;
        } else while (1);
    }
    return answer;
}

트리 게임(350점)

• 예상 난이도: 골드 상위
  
• 태그: 트리, 트리 DP, 애드혹

지문 요약

문제

루트 트리가 주어집니다.

형제 노드들끼리는 노드의 번호를 기준으로 정렬되어 있다고 가정하고 설명하겠습니다.

자식이 있는 각 노드들은 자식과 연결하는 간선 중 하나만 활성화됩니다. 처음에는 노드의 번호가 가장 작은 자식 노드 쪽 간선만 활성화되어 있습니다.

트리의 루트에서 숫자 1 또는 2 또는 3을 떨어뜨립니다. 떨어지는 숫자는 활성화된 간선들을 따라 떨어집니다. 숫자가 리프 노드까지 떨어지고 나면, 떨어진 경로 위의 활성화되어 있던 간선들은 활성화 방향을 바꿉니다.

어떻게 바꾸냐면 형제 노드 중 다음으로 큰 번호로 바꾸거나, 더 큰 번호가 없을 경우 가장 작은 번호로 바꿉니다. 만약 형제 노드가 없다면 활성화를 유지합니다.

 

그렇게 차례대로 숫자를 떨어뜨리는 시행을 반복해서 각 리프 노드마다 떨어진 숫자들을 합합니다.

리프 노드마다 만들어야 하는 합이 주어질 때, 만들 수 있는지 확인하고 만들 수 있다면 시행을 나열했을 때 사전순으로 가장 작은 형태가 되도록 구성하여 출력하세요.

 

모호한 부분이 있다면 언제든지 질문해주세요.

제약

$|E|\le 100$입니다. 트리의 루트는 항상 1입니다.

리프 노드마다 만들어야 하는 합은 $100$을 넘지 않습니다.

풀이

숫자가 떨어져 도달하는 리프 노드는 처음 도달되는 시점이 있을 것이고, 일정 사이클도 존재할 것입니다.

그 두 가지를 결정하고 나면 사전순으로 빨라야 하는 조건에 따라 최대한 앞을 1로 채우고 맨 뒤에만 3으로 몰면서, 기우성에 따라 경계를 2로 결정하거나 말거나 하면 될 겁니다.

 

아무튼 첫 도달 시점과 사이클만 구하면 어찌저찌 풀 수 있다는 건데요,

이 둘은 트리 DP로 구할 수 있습니다.

코드

구현이 까다롭습니다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 105;
const ll INF = 1e9;
int n;
ll S[N], T[N], C[N];
bool isLeaf[N];
vector<int> adj[N];

void dfs(int s = 1, int e = 0) {
    int _ = 0;
    if (siz(adj[s]) == 1) isLeaf[s] = true;
    sort(all(adj[s]));
    for (auto u : adj[s]) if (u != e) {
        C[u] = min(INF,C[s]+_*T[s]);
        S[u] = min(INF,C[s]+T[s]*(_++)+1);
        T[u] = min(INF,T[s]*(siz(adj[s])-1));
        dfs(u,s);
    }
}

vector<int> solution(vector<vector<int>> edges, vector<int> target) {
    vector<int> answer;
    n = siz(edges)+1;
    for (auto &v : edges) {
        adj[v[0]].push_back(v[1]);
        adj[v[1]].push_back(v[0]);
    }
    S[1] = 1, T[1] = 1, adj[1].push_back(0);
    dfs();
    ll least_length = 0, most_length = INF;
    rep(i,1,n) if (isLeaf[i]) {
        if (target[i-1] == 0) {
            mup(most_length,S[i]-1);
            continue;
        }
        Mup(least_length,min(INF,S[i]+((target[i-1]-1)/3)*T[i]));
    }
    if (least_length == INF) return {-1};
    if (least_length > most_length) return {-1};
    rep(i,1,n) if (isLeaf[i]) {
        int cnt = 0;
        for (int j = S[i]; j <= least_length; j += T[i]) cnt++;
        if (cnt > target[i-1]) {
            return {-1};
        }
    }
    answer.resize(least_length);
    rep(i,1,n) if (isLeaf[i]) {
        int c = target[i-1];
        int last_j = 0;
        for (int j = S[i]; j <= least_length; j += T[i]) {
            answer[j-1]++, c--;
            Mup(last_j,j);
        }
        for (int j = last_j; j >= S[i]; j -= T[i]) {
            if (c >= 2) answer[j-1] += 2, c -= 2;
            else if (c >= 1) answer[j-1]++, c--;
            else break;
        }
    }
    return answer;
}