전공자 Java코스로 신청했고, scpc로 인해서 삼성스타일은 잘 알기 때문에 딱히 준비하지는 않았다.
생각보다 더 난이도가 낮았던 기억이 있다.
오전/오후반이 나뉘는데, 주변 얘기를 들어보니 오후반이 더 쉬웠던 것 같다. 오전반 문제들의 열화판 정도로 느껴졌다.
코테에 합격했고, 면접까지 붙어서 최종 합격했다. 면접 후기는 나중에 시간이 남을 때 쓰려고한다.
최종 합격 하기는 했지만, 안타깝게도 다른 기업에 최종 합격하는 바람에 입과포기를 했다.
전공 시험도 포기하면서까지 참여한 것이라 조금 아깝긴 하지만, 나름 좋은 경험이었다고 생각한다.
특히 PT면접이 처음인데다가 준비를 정말 말 그대로 하나도 안 해서(어떤 식으로 진행되는지도 제대로 모르고 들어갔다..) 긴장을 많이 했는데, 생각보다 말을 잘 했고, 끝나고 나니 재밌었다는 생각이 들 정도였었다.
주변에 SSAFY 준비하던 지인들 모두 합격해서 입과 했는데, 괜히 뿌듯하고 기분이 좋다.
# 1. 로봇 모으기
$M \times M$ 격자칸에 로봇이 위치한다. 격자판에 총 3가지의 연산을 할 수 있는데, 모든 로봇들을 1칸 위로 움직이거나 왼쪽 또는 오른쪽으로 움직이는 것이다. 격자판의 끝에 도달한 로봇들은 격자판밖으로 나가지 않고, 가만히 있게 된다.
모든 로봇들이 한 점에서 모이도록 하는 최소 연산 횟수를 구하는 문제다. 단, 모든 로봇의 행이 같거나 열이 같은 경우는 주어지지 않는다.
아래로 움직이는 연산 없이 위, 좌, 우로만 움직일 수 있다. 게다가 문제의 마지막 조건에 의해 로봇의 행이 모두 같거나 열이 모두 같은 경우는 입력으로 들어오지 않으므로 좌상 또는 우상으로 한 점이 모일 수 밖에 없다.
두 경우 모두 ‘상’에서 모여야 하므로 가장 아래에 있는(행이 가장 큰) 로봇이 1번째 행에 도달할 때 까지 up 연산을 해야한다. 그리고 좌 또는 우로 몰아 주어야하는데,
- 좌로 몰아줄 경우, 가장 오른쪽에 있는(열이 가장 큰) 로봇이 1번째 열에 도달해야 하므로 열이 가장 큰 로봇의 좌표를 구한다.
- 우로 몰아줄 경우, 가장 왼쪽에 있는(열이 가장 작은) 로봇이 $m$번째 열에 도달해야 하므로 열이 가장 작은 로봇의 좌표를 구한다.
두 경우 중 가장 작은 경우가 정답이 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define INF (INT_MAX / 2)
#define MAX_N 305
int m, n;
void solve() {
cin >> m >> n;
int yMax = 0;
int xMin = INF;
int xMax = 0;
for (int i = 0; i < n; ++i) {
pii robot;
cin >> robot.first >> robot.second;
yMax = max(yMax, robot.first);
xMin = min(xMin, robot.second);
xMax = max(xMax, robot.second);
}
cout << (yMax - 1) + min(xMax - 1, m - xMin) << endl;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(false);
int testcase;
cin >> testcase;
for (int tc = 1; tc <= testcase; ++tc) {
cout << "#" << tc << ' ';
solve();
}
return 0;
}
# 2. 욕심쟁이
$N$개의 칸에 보석이 있거나 또는 없을 수 있다. 욕심쟁이는 첫 시작점 $M$에서 출발하여 가장 가까운(좌 또는 우로) 보석을 찾아 가진 뒤, 그 자리에서 다시 가장 가까운 보석을 찾아 가지는 일을 모든 보석을 얻을 때 까지 반복한다.
그런데, 어떤 위치에서 가장 가까운 보석이 두 개일 때(좌, 우 모두 같은 거리에 있는 경우), 욕심쟁이는 더 이상 움직이지 못 하고 멈춰버린다. 시작 지점 $M$에서 시작하는 경우 더 이상 움직이지 못 하고 멈춰버리는 경우가 생길 수도 있다.
모든 보석을 얻을 수 있는 지점 $x$가 $M$으로 부터 $i$만큼 떨어져있다고 하자. 그런 최소 $i$를 구하는 문제다.
모든 점 $x$를 하나하나 돌아가며 그 점에서 규칙대로 움직였을 때 모든 보석을 얻을 수 있는지 여부에 따라 정답을 갱신해나가면 된다. 점 $x$순회에 $O(N)$, 각 점에서 출발하는 경우를 탐색하고, $O(N)$에 가장 가까운 보석을 찾을 수 있으며, 보석이 최대 $N$개 있으므로 $O(N^3)$에 풀 수 있다. $N = 300$이므로 충분히 가능하지만, set을 이용한 이분탐색을 사용하면 $O(N^2 log_{2}(N))$에 풀 수있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define INF (INT_MAX / 2)
#define MAX_N 305
int m, n;
set<int> jwerleyIdxOriginal;
pii findNearPair(const set<int>& jwerleyIdx, int from) {
pii ret = {-INF, INF};
auto leftIter = jwerleyIdx.lower_bound(from);
auto rightIter = leftIter;
--leftIter;
if (leftIter != jwerleyIdx.end()) {
ret.first = *leftIter;
}
if (rightIter != jwerleyIdx.end()) {
ret.second = *rightIter;
}
return ret;
}
bool isBoom(const pii& nearPair, int here) {
if (nearPair.first == nearPair.second) return false;
return abs(here - nearPair.first) == abs(here - nearPair.second);
}
int getNearest(const pii& nearPair, int here) {
int lDist = abs(here - nearPair.first);
int rDist = abs(here - nearPair.second);
if (lDist < rDist) {
return nearPair.first;
} else {
return nearPair.second;
}
}
bool run(int startPos) {
set<int> jwerleyIdx = jwerleyIdxOriginal;
int here = startPos;
while (jwerleyIdx.size()) {
pii nearPair = findNearPair(jwerleyIdx, here);
if (isBoom(nearPair, here)) {
return false;
}
int nearest = getNearest(nearPair, here);
jwerleyIdx.erase(nearest);
here = nearest;
}
return true;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
bool jwerlyPlaced;
cin >> jwerlyPlaced;
if (jwerlyPlaced) {
jwerleyIdxOriginal.emplace(i);
}
}
int ans = 0;
for (ans = 0; ans < n; ++ans) {
int lPos = m - ans;
int rPos = m + ans;
bool res = false;
if (lPos >= 1) {
res |= run(lPos);
}
if (rPos <= n) {
res |= run(rPos);
}
if (res) break;
}
cout << ans << endl;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(false);
int testcase;
cin >> testcase;
for (int tc = 1; tc <= testcase; ++tc) {
cout << "#" << tc << ' ';
jwerleyIdxOriginal.clear();
solve();
}
return 0;
}