PS 부수기
2022 KAKAO BLIND RECRUITMENT 코테 후기 본문
A. 서로 신고하는 문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
using pii = pair<int, int>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
vector<int> solution(vector<string> id_list, vector<string> report, int k) {
vector<int> answer;
int n = sz(id_list);
int m = sz(report);
answer = vector<int>(n);
map<string, int> mp;
for(int i=0 ; i<n ; i++) {
mp[id_list[i]] = i;
}
vector<vector<int>> a(n);
vector<int> cnt(n);
for(int i=0 ; i<m ; i++) {
int spcidx = -1;
for(int j=0 ; j<sz(report[i]) ; j++) {
if(report[i][j] == ' ')
spcidx = j;
}
string gahae = report[i].substr(0, spcidx);
string pihae = report[i].substr(spcidx + 1, sz(report[i]) - sz(gahae) - 1);
int gaidx = mp[gahae];
int piidx = mp[pihae];
a[gaidx].push_back(piidx);
}
for(int i=0 ; i<n ; i++) {
uniq(a[i]);
for(auto x : a[i])
cnt[x]++;
}
for(int i=0 ; i<n ; i++) {
for(auto x : a[i]) {
if(cnt[x] >= k)
answer[i]++;
}
}
return answer;
}
|
cs |
개극혐구현
B. k진수 후 소수판별문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
using pii = pair<int, int>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
bool is_prime(ll x) {
if(x == 1)
return false;
for(ll i=2 ; i*i<=x ; i++) {
if(x%i==0)
return false;
}
return true;
}
int solution(int n, int k) {
int answer = 0;
vector<int> a;
int orign = n;
while(n > 0) {
a.push_back(n % k);
n /= k;
}
reverse(all(a));
ll c = 0;
vector<ll> num;
for(int i=0 ; i<sz(a) ; i++) {
if(a[i] == 0) {
if(c != 0)
num.push_back(c);
c = 0;
} else {
c *= 10;
c += a[i];
}
}
if(c!=0)
num.push_back(c);
for(int i=0 ; i<sz(num) ; i++) {
if(is_prime(num[i]))
answer++;
}
return answer;
}
|
cs |
n -> k진법으로 변환 -> 0을 기준으로 10진법으로 변환 -> 각 숫자 소수판별
.. 결국 구현
C. 차 넣고 빼는 문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
using pii = pair<int, int>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
vector<int> fees;
vector<string> records;
vector<int> times, nums, inout;
vector<int> recenttime(10000, -1), tt(10000);
vector<int> solution(vector<int> fees_, vector<string> records_) {
fees = fees_;
records = records_;
vector<int> answer;
int n = sz(records);
times = vector<int>(n);
nums = vector<int>(n);
inout = vector<int>(n);
for(int i=0 ; i<n ; i++) {
string s = records[i];
int h = 10 * (s[0] - '0') + s[1] - '0';
int m = 10 * (s[3] - '0') + s[4] - '0';
int t = h * 60 + m;
times[i] = t;
int cnum = (s[6]-'0') * 1000 + (s[7]-'0') * 100 + (s[8]-'0') * 10 + s[9]-'0';
nums[i] = cnum;
if(s[11] == 'I')
inout[i] = 1;
else
inout[i] = 2;
}
int kibonT = fees[0];
int kibonFee = fees[1];
int danwiT = fees[2];
int danwiFee = fees[3];
for(int i=0 ; i<n ; i++) {
int carNum = nums[i];
int carTime = times[i];
if(inout[i] == 1) {
recenttime[carNum] = carTime;
} else {
int timeFlowed = carTime - recenttime[carNum];
tt[carNum] += timeFlowed;
recenttime[carNum] = -1;
}
}
for(int i=0 ; i<=9999 ; i++) {
if(recenttime[i] != -1) {
tt[i] += 1439-recenttime[i];
}
}
for(int i=0 ; i<=9999 ; i++) {
if(tt[i] == 0) continue;
else {
if(tt[i] <= kibonT) {
answer.push_back(kibonFee);
} else {
int aaa = 0;
aaa += kibonFee;
tt[i] -= kibonT;
if(tt[i] % danwiT == 0) {
aaa += (tt[i] / danwiT) * danwiFee;
} else {
aaa += (tt[i] / danwiT + 1) * danwiFee;
}
answer.push_back(aaa);
}
}
}
return answer;
}
|
cs |
개같은 구현
D. 활쏘는 문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
using pii = pair<int, int>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
vector<int> solution(int n, vector<int> info) {
vector<int> answer;
int mxdif = 0;
bool fail = true;
int mxjsc = -INF;
for(int mask = 0 ; mask < 1024 ; mask++) {
int need = 0;
vector<int> st(11);
for(int i=0 ; i<10 ; i++) {
if((mask >> i) & 1) {
need += info[i] + 1;
st[i] = info[i] + 1;
}
}
if(need > n)
continue;
st[10] = n - need;
int jsc = 0;
for(int i=0 ; i<10 ; i++) {
if(info[i] < st[i])
jsc += 10-i;
else if(info[i] > 0)
jsc -= 10-i;
}
if(mxjsc < jsc) {
answer = st;
mxjsc = jsc;
} else if(mxjsc == jsc) {
for(int i=10 ; i>=0 ; i--) {
if(st[i] > answer[i]) {
answer = st;
break;
}
}
}
if(jsc > 0) {
fail = false;
}
}
if(mxjsc<=0) {
vector<int> q;
q.push_back(-1);
return q;
}
return answer;
}
|
cs |
구현
E. 트리에서 양을 구하는 문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
using pii = pair<int, int>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
vector<vector<int>> G;
vector<int> info;
int solution(vector<int> info_, vector<vector<int>> edges) {
int answer = 0;
info = info_;
int n = sz(info);
G = vector<vector<int>> (n);
for(int i=0 ; i<sz(edges) ; i++) {
int u = edges[i][0], v = edges[i][1];
G[u].push_back(v);
G[v].push_back(u);
}
vector<bool> dp(1<<n, 0);
dp[1] = 1;
for(int mask = 1 ; mask < (1<<n) ; mask++) {
if(dp[mask] == false)
continue;
int tmp = mask, c = 0, y = 0, z = 0;
vector<bool> vis(n);
while(tmp > 0) {
if(tmp & 1) {
vis[c] = 1;
if(info[c] == 0) {
z++; y++;
}
else
y--;
}
c++;
tmp /= 2;
}
answer = max(answer, z);
vector<int> nxts;
for(int i=0 ; i<n ; i++) {
if(!vis[i]) continue;
for(int nxt : G[i]) {
if(vis[nxt]) continue;
nxts.push_back(nxt);
}
}
uniq(nxts);
for(int nxt : nxts) {
if(info[nxt] == 0) {
dp[mask | (1<<nxt)] = 1;
} else {
if(y > 1)
dp[mask | (1<<nxt)] = 1;
}
}
}
return answer;
}
|
cs |
방문 노드 상태가 mask -> 불가능 시 dp[mask] = INF, 가능 시 dp[mask] = 1
dp[mask]가 1인 mask 중 양의 갯수가 최대인 것이 답
F. 네모에 폭탄과 힐을 떨구는 문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
using pii = pair<int, int>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
int n = sz(board);
int m = sz(board[0]);
vector<vector<int>> prefix(n+1, vector<int>(m+1));
for(int i=0 ; i<sz(skill) ; i++) {
int type = skill[i][0];
int mul = (type == 1) ? -1 : 1;
int r1 = skill[i][1];
int c1 = skill[i][2];
int r2 = skill[i][3];
int c2 = skill[i][4];
int deg = skill[i][5];
prefix[r1][c1] += mul * deg;
prefix[r2 + 1][c1] -= mul * deg;
prefix[r1][c2 + 1] -= mul * deg;
prefix[r2 + 1][c2 + 1] += mul * deg;
}
for(int i=0 ; i<n ; i++) {
for(int j=0 ; j<m ; j++) {
prefix[i+1][j] += prefix[i][j];
prefix[i][j+1] += prefix[i][j];
prefix[i+1][j+1] -= prefix[i][j];
}
}
for(int i=0 ; i<n ; i++) {
for(int j=0 ; j<m ; j++) {
prefix[i][j] += board[i][j];
}
}
for(int i=0 ; i<n ; i++)
for(int j=0 ; j<m ; j++)
answer += (prefix[i][j] > 0);
return answer;
}
|
cs |
2차원 prefix sum 문제
G. 둘이서 판때기에서 지랄하는 문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
using pii = pair<int, int>;
using ll = long long;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
vector<vector<int>> board, orig_board;
vector<int> dx = {0,0,1,-1}, dy = {1,-1,0,0};
int n, m;
bool valid(int x, int y) {
return x >= 0 && y >= 0 && x < n && y < m && board[x][y] == 1;
}
pair<int,bool> dfs(pii a, pii b, int turn) {
if(turn == 0) {
if(board[a.ff][a.ss] == 0) {
return {0,0};
}
bool iwon = false;
bool moved = false;
int mxMove = 0;
int mnMove = INF;
for(int i=0 ; i<4 ; i++) {
int nx = a.ff + dx[i];
int ny = a.ss + dy[i];
if(!valid(nx, ny)) continue;
board[a.ff][a.ss] = 0;
pair<int, bool> res = dfs({nx,ny}, b, 1-turn);
board[a.ff][a.ss] = 1;
res.ff += 1;
iwon |= (!res.ss);
if(!res.ss) {
mnMove = min(mnMove, res.ff);
}
mxMove = max(mxMove, res.ff);
}
if(iwon) {
return {mnMove,1};
} else {
return {mxMove,0};
}
} else {
if(board[b.ff][b.ss] == 0) {
return {0,0};
}
bool iwon = false;
bool moved = false;
int mxMove = 0;
int mnMove = INF;
for(int i=0 ; i<4 ; i++) {
int nx = b.ff + dx[i];
int ny = b.ss + dy[i];
if(!valid(nx, ny)) continue;
board[b.ff][b.ss] = 0;
pair<int, bool> res = dfs(a, {nx,ny}, 1-turn);
board[b.ff][b.ss] = 1;
res.ff += 1;
iwon |= (!res.ss);
if(!res.ss) {
mnMove = min(mnMove, res.ff);
}
mxMove = max(mxMove, res.ff);
}
if(iwon) {
return {mnMove,1};
} else {
return {mxMove,0};
}
}
}
int solution(vector<vector<int>> board_, vector<int> aloc, vector<int> bloc) {
int answer = -1;
orig_board = board_;
board = board_;
n = sz(board);
m = sz(board[0]);
pii a, b;
a.ff = aloc[0], a.ss = aloc[1];
b.ff = bloc[0], b.ss = bloc[1];
pair<int, bool> k = dfs(a, b, 0);
answer=k.ff;
return answer;
}
|
cs |
dfs로 모든 경우의 수를 다 가면 된다.
메모이제이션이 없는 게임이론 dp로 풀엇다
후기
코테 특유의 쓸데없는 구현 문제가 너무 싫다.(그냥 입력으로 주면 될걸 문자열로 준다던지..)
그래도 머기업들이 그런 능력이 필요하니깐 냈겠지 싶었다.
E, G 번 문제는 재미있었다.
'PS' 카테고리의 다른 글
| 백준 12858 : Range GCD (1) | 2021.09.17 |
|---|---|
| 세그멘트트리 많이 보는 유형 3문제 (0) | 2021.09.14 |
| 백준 19851 - 버거운 버거 (0) | 2021.09.08 |
| 백준 20681 - Black Family Tree (0) | 2021.02.05 |
| Atcoder Japanese Student Championship 2019 Qualification - C(Cell inversion) (0) | 2021.02.05 |
'PS' Related Articles
more
Comments