14889 스타트와 링크 https://www.acmicpc.net/problem/14889
14890 경사로 https://www.acmicpc.net/problem/14890
14891 톱니바퀴 https://www.acmicpc.net/problem/14891
삼성 코딩 테스트 대부분은 bfs, dfs, 구현, 완전탐색 정도의 문제들이 많이 출제된다.
이 포스트에서는 17년 삼성 DS, CE/IM 기출문제를 다뤄보겠다.
1. 연산자 끼워넣기
N개의 수가 주어지고 N-1개의 연산자가 주어진다.
수 사이에 연산자를 끼워놓을 때 연산자 우선순위없이 결과값의 최댓값, 최솟값을 구하는 문제다.
N이 작으므로 완전탐색으로 답을 구할 수 있다.
#include <cstdio>
#include <algorithm>
using namespace std;
int N;
int arr[11];
int Plus, Minus, Mul, Mod;
int Min = 1000000001, Max = -1000000001;
void solve(int idx, int sum, int plus, int minus, int mul, int mod) {
if (idx == N) {
Min = min(Min, sum);
Max = max(Max, sum);
return;
}
if (plus) solve(idx + 1, sum + arr[idx], plus - 1, minus, mul, mod);
if (minus) solve(idx + 1, sum - arr[idx], plus, minus - 1, mul, mod);
if (mul) solve(idx + 1, sum*arr[idx], plus, minus, mul - 1, mod);
if (mod) solve(idx + 1, sum / arr[idx], plus, minus, mul, mod - 1);
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d", &arr[n]);
scanf("%d%d%d%d", &Plus, &Minus, &Mul, &Mod);
solve(1, arr[0], Plus, Minus, Mul, Mod);
printf("%d\n%d\n", Max, Min);
return 0;
}
| cs |
2. 스타트와 링크
N명의 사람들을 N/2로 이루어진 두 팀으로 나눌 때 팀의 능력치의 차이 최소값을 구하는 문제다.
팀의 능력치는 팀에 속한 사람들 쌍의 능력치의 합이다.
dp, 완전탐색으로 풀 수 있다.
dp로 풀었을 때는 BOJ기준으로 시간이 1초 넘게 소모된다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 987654321
int N;
int dp[1 << 20];
int map[21][21];
bool count(int info) {
int cnt = 0;
for (int n = 0;n < N;n++) {
if (info & (1 << n)) cnt++;
}
return cnt == N / 2;
}
int getScore(int info) {
int start = 0, link = 0;
for (int n = 0;n < N;n++) {
if (info & (1 << n)) {
for (int m = n + 1;m < N;m++) {
if (info & (1 << m)) {
start += (map[n][m] + map[m][n]);
}
}
}
else {
for (int m = n + 1;m < N;m++) {
if (!(info & (1 << m))) {
link += (map[n][m] + map[m][n]);
}
}
}
}
return abs(start - link);
}
int solve(int info) {
if (count(info)) return dp[info] = getScore(info);
int &ret = dp[info];
if (ret != -1) return ret;
ret = INF;
for (int n = 0;n < N;n++) {
if (info & (1 << n)) continue;
ret = min(ret, solve(info | (1 << n)));
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d", &N);
for (int n = 0;n < N;n++)for (int m = 0;m < N;m++) scanf("%d", &map[n][m]);
printf("%d\n", solve(0));
return 0;
}
| cs |
완전탐색으로 하는게 더 빠르다.
#include <cstdio>
inline int min(int a, int b) { return a < b ? a : b; }
inline int abs(int x) { return x < 0 ? -x : x; }
int N;
int map[20][20];
int ans = 0x3f3f3f3f;
void solve(int a, int b, int st1, int st2, int info1, int info2, int pivot) {
if (a + b == N) {
ans = min(ans, abs(st1 - st2));
return;
}
int plus = 0;
if (a < N / 2) {
for (int m = 0;m < N;m++) {
if (info1 & (1 << m)) plus += (map[pivot][m] + map[m][pivot]);
}
solve(a + 1, b, st1 + plus, st2, (info1 | (1 << pivot)), info2, pivot + 1);
}
if (b < N / 2) {
plus = 0;
for (int m = 0;m < N;m++) {
if (info2 & (1 << m)) plus += (map[pivot][m] + map[m][pivot]);
}
solve(a, b + 1, st1, st2 + plus, info1, (info2 | (1 << pivot)), pivot + 1);
}
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++)for (int m = 0;m < N;m++) scanf("%d", &map[n][m]);
solve(0, 0, 0, 0, 0, 0, 0);
printf("%d\n", ans);
return 0;
}
| cs |
3. 경사로
문제 요약 생략
시작점에서 경사로만큼 내려가거나 올라갈 수 있는경우, 높이가 같은경우로 이동시키듯 구현했다.
나머지 자잘한 예외처리도 해줘야한다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N, L;
int map[101][101];
bool v[101];
int ans = 0;
void solve() {
for (int n = 0;n < N;n++) {
memset(v, false, sizeof v);
int prev = map[n][0];
int s = 1;
while (s) {
if (s == N) { ans++; break; }
if (map[n][s] == prev) s++;
else {
if (map[n][s] == prev - 1) { //감소
if (s + L - 1 >= N) break;
bool go = true;
for (int m = s;m <= s + L - 1;m++) {
if (map[n][m] != map[n][s] || v[m]) { go = false; break; }
}
if (go) {
for (int m = s;m <= s + L - 1;m++) v[m] = true;
s = s + L, prev--;
}
else break;
}
else if (map[n][s] == prev + 1) { //증가
if (s - L < 0) break;
bool go = true;
for (int m = s - L;m < s;m++) {
if (map[n][m] != map[n][s] - 1 || v[m]) { go = false; break; }
}
if (go) {
for (int m = s - L;m < s;m++) v[m] = true;
s = s + 1, prev++;
}
else break;
}
else break;
}
}
}
}
int main() {
scanf("%d%d", &N, &L);
for (int n = 0;n < N;n++) for (int m = 0;m < N;m++) scanf("%d", &map[n][m]);
solve();
for (int n = 0;n < N;n++) for (int m = n + 1;m < N;m++) swap(map[n][m], map[m][n]);
solve();
printf("%d\n", ans);
return 0;
}
| cs |
4. 톱니바퀴
문제 요약 생략
젤 재밌었던 문제다.
bitmask에 저장해서 회전하는것을 shift연산으로 해줬다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 4, M = 8;
int Q;
int s[4] = { 0 };
void change(int num, int dir) {
if (dir == 1) {
int save = (s[num] & (1 << 7)) > 0 ? 1 : 0;
s[num] <<= 1;
if (save && !(s[num] & (1 << 0))) s[num] |= (1 << 0);
}
else {
int save = (s[num] & (1 << 0)) > 0 ? 1 : 0;
s[num] >>= 1;
if (save && !(s[num] & (1 << 7))) s[num] |= (1 << 7);
}
}
//dir : 시계 or 반시계 or 정지
//왼쪽
void solve1(int num, int dir) {
if (num == -1) return;
int prev = (s[num + 1] & (1 << 6)) > 0 ? 1 : 0;
int here = (s[num] & (1 << 2)) > 0 ? 1 : 0;
if (prev == here) return;
else {
solve1(num - 1, -dir);
change(num, -dir);
}
}
//오른쪽
void solve2(int num, int dir) {
if (num == N) return;
int prev = (s[num - 1] & (1 << 2)) > 0 ? 1 : 0;
int here = (s[num] & (1 << 6)) > 0 ? 1 : 0;
if (prev == here) return;
else {
solve2(num + 1, -dir);
change(num, -dir);
}
}
int main() {
for (int n = 0;n < N;n++) {
int in;
for (int m = 0;m < M;m++) {
scanf("%1d", &in);
if (in) s[n] |= (1 << m);
}
}
scanf("%d", &Q);
while (Q--) {
int num, dir;
scanf("%d%d", &num, &dir);
num--;
solve1(num - 1, dir);
solve2(num + 1, dir);
change(num, dir);
}
int ans = 0;
for (int n = 0, score = 1;n < N;n++, score *= 2) {
if (s[n] & (1 << 0)) ans += score;
}
printf("%d\n", ans);
return 0;
}
| cs |
