2017 삼성 S/W 역량 테스트 기출문제

14888 연산자 끼워넣기 https://www.acmicpc.net/problem/14888
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; } Colored by Color Scripter

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; } Colored by Color Scripter

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; } Colored by Color Scripter

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; } Colored by Color Scripter

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; } Colored by Color Scripter

cs