Notice
Recent Posts
천천히 빛나는
삼성 SW 기초 문제 (1) 본문
본 포스팅에서는 [시험감독, 연산자 끼워넣기, 로봇 청소기, 톱니바퀴, 미세먼지 안녕!, 감시, 뱀]을 다룹니다.
13458. (시험 감독) 각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int n;
int a;
double b, c;
vector<int>v;
int main() {
cin >> n;
while (n--) {
cin >> a;
v.push_back(a);
}
cin >> b >> c;
long long total = v.size();
for (int i = 0; i < v.size(); i++)
{
if (v[i] - b > 0)
total += int(ceil((v[i] - b) / c));
}
cout << total;
return 0;
}어렵지 않은 아주 간단한 문제인데 자꾸 변수 타입 설정에서 틀린다. long long이 필요한지 아닌지 판단하는 걸 더 키워야 할 거 같다.
14888. (연산자 끼워넣기) 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다. N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
#include<iostream>
#include<vector>
#include<stack>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int nOp = 0;
vector<int>v;
for (int i = 0; i < 4; i++)
{
cin >> nOp;
for (int j = 0; j < nOp; j++)
{
v.push_back(i + 1);
}
}
int maxNum = -1000000001;
int minNum = 1000000001;
do {
int result = a[0];
for (int i = 0; i < v.size(); i++)
{
if (v[i] == 1) {
result += a[i + 1];
}
else if (v[i] == 2) {
result -= a[i + 1];
}
else if (v[i] == 3) {
result *= a[i + 1];
}
else {
result /= a[i + 1];
}
}
maxNum = max(maxNum, result);
minNum = min(minNum, result);
} while (next_permutation(v.begin(), v.end()));
cout << maxNum << '\n' << minNum;
}연산기호를 순열로 만들고 next_permutation 함수를 사용하였다.
bool next_permutation (첫번째 주소, 마지막 주소);
bool next_permutation (첫번째 주소, 마지막 주소, Compare 함수);next_permutation을 사용할 때는 오름차순으로 정렬된 값을 가진 벡터로만 가능하고 default로 오름차순으로 순열을 생성하게 된다. 중복이 있는 원소를 제외하고 순열이 만들어지며 순열이 만들어졌을 경우 true를 반환한다.
https://mjmjmj98.tistory.com/38
[C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기
순열을 구하는 next_permutation 함수 순열 수학적으로 순열(permutation)이란 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말합니다. 원소를 한 줄로 세우기 때문에 원소의 조합이
mjmjmj98.tistory.com
대부분 DFS, 백트래킹으로 풀었길래 DFS에 대한 이해가 부족하다는 생각이 들었다. 백트래킹 공부를 좀 더 하고 코드를 작성해보았다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int minN = 1000000001;
int maxN = -1000000001;
int n;
vector<int>v;
vector<int>operate;
void calculation(int result, int idx) {
if (idx == v.size()) { // 연산기호 남은거 없음
maxN = max(maxN, result);
minN = min(minN, result);
return;
}
if (operate[0]) {
operate[0]--;
calculation(result + v[idx], idx + 1);
operate[0]++;
}
if (operate[1]) {
operate[1]--;
calculation(result - v[idx], idx + 1);
operate[1]++;
}
if (operate[2]) {
operate[2]--;
calculation(result * v[idx], idx + 1);
operate[2]++;
}
if (operate[3]) {
operate[3]--;
calculation(result / v[idx], idx + 1);
operate[3]++;
}
}
int main() {
cin >> n;
while (n--) {
int x;
cin >> x;
v.push_back(x);
}
for (int i = 0; i < 4; i++)
{
int x;
cin >> x;
operate.push_back(x);
}
calculation(v[0], 1);
cout << maxN << '\n' << minN;
}DFS과 백트래킹을 이용해서 구현할 수 있다.
예를 들어 3 4 5 / 1 0 1 0이 입력되었다고 가정하면 이런식으로 작동하게 된다.
14503. 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int n, m, r, c, d;
int room[50][50];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0 , 1, 0, -1 };
int cnt = 0;
void cleaning(int row, int col, int direction) {
if (row < 0 || row >= n || col < 0 || col >= m)
return;
if (room[row][col] == -1) {
int newD = (direction - 1 >= 0) ? direction - 1 : 3;
// int newD = direction;
bool flag = 0;
for (int i = 0; i < 4; i++)
{
if (room[row + dx[newD]][col + dy[newD]] == 0) {
flag = 1;
break;
}
newD = (newD - 1 >= 0) ? newD - 1 : 3;
}
if (flag==0) {
int opposite = (2 + direction <= 3) ? 2 + direction : direction - 2;
//cout << "원방향: " << direction << "갈방향: " << opposite << endl;
if (room[row + dx[opposite]][col + dy[opposite]] == 1) {
//cout << row + dx[opposite] <<"," << row + dx[opposite]<< "는 벽입니다. 종료합니다.\n";
return;
}
else {
//cout << row + dx[opposite] << "," << col + dy[opposite] << "로 반대쪽 이동을 합니다.\n";
cleaning(row + dx[opposite], col + dy[opposite], direction);
}
}
else {
cleaning(row + dx[newD], col + dy[newD], newD);
}
}
else if (room[row][col] == 0) {
room[row][col] = -1;
cnt++;
//cout << row << "," << col << "을 청소합니다.\n";
cleaning(row, col, direction);
}
}
int main() {
cin >> n >> m;
cin >> r >> c >> d;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> room[i][j];
}
}
cleaning(r, c, d);
cout << cnt;
}재귀함수를 사용해서 풀었다. cout 주석을 풀면 어떤식으로 동작하는지 알 수 있다.
14891. (톱니바퀴) 톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
string rail[5];
int num, dir;
bool visited[5];
int up[5];
void rotation(int n, int d) {
visited[n] = 1;
if (n+1 <=4 && !visited[n + 1]) {
char secondNow = rail[n][(up[n] + 2) % 8];
char sixthNext = rail[n + 1][(up[n + 1] + 6) % 8];
if (secondNow != sixthNext) {
int newR = 0 - d;
rotation(n + 1, newR);
if (newR == 1) // 시계
up[n + 1] = (up[n + 1] + 7) % 8;
else
up[n + 1] = (up[n + 1] + 1) % 8;
}
}
if (n-1 > 0 && !visited[n - 1]) {
char sixthNow = rail[n][(up[n] + 6) % 8];
char secondNext = rail[n - 1][(up[n - 1] + 2) % 8];
if (sixthNow != secondNext) {
int newR = 0 - d;
rotation(n - 1, newR);
if (newR == 1) // 시계
up[n - 1] = (up[n - 1] + 7) % 8;
else
up[n - 1] = (up[n - 1] + 1) % 8;
}
}
if (num == n) {
if (d == 1)
up[n] = (up[n] - d + 8) % 8;
else
up[n] = (up[n] - d) % 8;
}
}
int main() {
// 2, 6
for (int i = 1; i <= 4; i++)
{
cin >> rail[i];
}
int k;
cin >> k;
while (k--) {
cin >> num >> dir;
rotation(num, dir);
for (int i = 1; i < 5; i++)
{
visited[i] = 0;
}
}
int sum = 0;
for (int i = 1; i <= 4; i++)
{
sum += (rail[i][up[i]] - '0') * pow(2,i-1);
}
cout << sum;
}회전을 표현하기 위해 덱을 사용하시는 분들도 많았다. 나는 + 이동 % 사이즈를 사용하고 12시 방향에 있는게 누구인지 저장하는 배열을 따로 만들었다.
17144. (미세먼지 안녕!) 방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
int r, c, t;
int map[51][51];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int airclean;
void air() {
queue<pair<pair<int, int>, int>>q;
while (t--) {
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
if (map[i][j] > 0) {
int count = 0;
int air = map[i][j] / 5;
for (int k = 0; k < 4; k++)
{
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
if (map[nx][ny] != -1) {
//cout << nx << "," << ny << "에 " << air << "추가중 \n";
q.push({ { nx, ny }, air });
count++;
}
}
}
q.push({ { i, j }, 0 - (air * count) });
}
}
}
while (!q.empty()) {
int x = q.front().first.first;
int y = q.front().first.second;
int airP = q.front().second;
q.pop();
map[x][y] += airP;
}
q.push({ {airclean - 1, 1}, 0 });
q.push({ {airclean, 1}, 0 });
for (int i = 2; i < c; i++)
{
q.push({ {airclean - 1, i}, map[airclean - 1][i - 1] });
}
for (int i = airclean - 2; i >= 0; i--)
{
q.push({ {i, c - 1}, map[i + 1][c - 1] });
}
for (int i = c - 2; i >= 0; i--)
{
q.push({ {0, i},map[0][i + 1] });
}
for (int i = 1; i < airclean - 1; i++)
{
q.push({{ i, 0 }, map[i - 1][0]});
}
for (int i = 2; i < c; i++)
{
q.push({ {airclean, i}, map[airclean][i - 1] });
}
for (int i = airclean+1; i < r; i++)
{
q.push({ {i, c - 1}, map[i - 1][c - 1] });
}
for (int i = c-2; i >=0; i--)
{
q.push({ {r - 1, i},map[r - 1][i + 1] });
}
for (int i = r - 2; i >= airclean + 1; i--)
{
q.push({ {i, 0}, map[i + 1][0] });
}
while (!q.empty()) {
int x = q.front().first.first;
int y = q.front().first.second;
int airNew = q.front().second;
q.pop();
map[x][y] = airNew;
}
}
}
int main() {
cin >> r >> c >> t;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> map[i][j];
if (map[i][j] == -1) {
airclean = i;
}
}
}
air();
int sum = 0;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
// cout << map[i][j] << " ";
if (map[i][j] != -1)
sum += map[i][j];
}
// cout << endl;
}
cout << sum << endl;
}나는 queue를 만들어서 이후에 해야할 일을 저장해두었다.
15683. (감시) 사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
#include<iostream>
#include<vector>
using namespace std;
int map[8][8];
bool visited[8][8];
int n, m;
int block;
int result = 100;
vector <pair<int, int> > cctvRC;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
// 0오른 1뒤 2왼 3위
void detect(int row, int col, int direction) {
if (row < 0 || row >= n || col < 0 || col >= m)
return;
if (map[row][col] == 6) {
return;
}
visited[row][col] = 1;
detect(row + dx[direction], col + dy[direction], direction);
}
void cctv(int idx) {
if (idx == cctvRC.size()) {
int cnt = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j] == 0 && map[i][j] == 0)
cnt++;
}
}
result = min(cnt, result);
return;
}
int x = cctvRC[idx].first;
int y = cctvRC[idx].second;
bool temp[8][8];
for (int dir = 0; dir < 4; dir++) // 회전시키기
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
temp[i][j] = visited[i][j];
}
}
if (map[x][y] == 1)
detect(x, y, dir);
else if (map[x][y] == 2) {
detect(x, y, dir % 4);
detect(x, y, (dir + 2) % 4);
}
else if (map[x][y] == 3) {
detect(x, y, dir % 4);
detect(x, y, (dir + 1) % 4);
}
else if (map[x][y] == 4) {
detect(x, y, dir % 4);
detect(x, y, (dir + 1) % 4);
detect(x, y, (dir + 2) % 4);
}
else if (map[x][y] == 5) {
detect(x, y, dir % 4);
detect(x, y, (dir + 1) % 4);
detect(x, y, (dir + 2) % 4);
detect(x, y, (dir + 3) % 4);
}
cctv(idx + 1);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
visited[i][j] = temp[i][j]; // 전단계로 돌아가기
}
}
}
}
int main() {
cin >> n >> m;
block = n * m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> map[i][j];
if (map[i][j] > 0 && map[i][j] < 6)
cctvRC.push_back({ i, j });
}
}
cctv(0);
cout << result;
}dfs를 이용한 풀이이다.
동작 순서를 이런 식으로 나타낼 수 있다. 단 그림에선 2번 카메라의 방향 종류가 2개 뿐이지만 위 코드에서는 4개로 중복되는 경로가 생기긴한다.
파란색으로 표시한 cctv 함수가 같은 함수인 것이다. 즉 하나의 함수 안에서 그 사이에 있던 명령들이 일어났다고 생각하면 된다.
DFS 문제는 조금 까다로운 것 같다. 다양한 DFS 문제를 풀어봐야겠다는 생각이 들었다.
3190. (뱀) 사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
#include<iostream>
#include<queue>
#include<deque>
using namespace std;
int n, k, l;
int map[101][101];
int cnt;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
queue<pair<int, char>>rotation;
deque<pair<int, int>>xyS;
void snake(int row, int col, int d) {
if (!rotation.empty() && cnt == rotation.front().first) {
if (rotation.front().second == 'L') {
d = ((d - 1) + 4) % 4;
}
else {
d = (d + 1) % 4;
}
rotation.pop();
}
int nx = row + dx[d];
int ny = col + dy[d];
if (nx <= 0 || nx > n || ny <= 0 || ny > n) {
cnt++;
return;
}
if (map[nx][ny] == 1) {
cnt++;
return;
}
xyS.push_front({ nx,ny });
// cout << nx << "," << ny << "로 머리 이동\n";
cnt++;
if (map[nx][ny] != 2) {
int tailx = xyS.back().first;
int taily = xyS.back().second;
// cout << tailx << "," << taily << "의 꼬리 삭제\n";
map[tailx][taily] = 0;
xyS.pop_back();
}
map[nx][ny] = 1;
snake(nx, ny, d);
}
int main() {
cin >> n >> k;
while (k--) {
int x, y;
cin >> x >> y;
map[x][y] = 2;
}
cin >> l;
while (l--) {
int x;
char y;
cin >> x >> y;
rotation.push({ x, y });
}
xyS.push_front({ 1,1 });
snake(1, 1, 1);
cout << cnt;
}사과가 있는 칸은 2를 넣어줬다. 몸의 길이가 늘어나면 deque에 추가해줬고 map에 1로 표시해주었다.
'C++ > SAMSUNG (C++)' 카테고리의 다른 글
| 삼성 SW 기출 문제 (3) (0) | 2023.10.14 |
|---|---|
| 삼성 SW 기출 문제 (2) (1) | 2023.10.13 |
| 삼성 SW 기출 문제 (1) (0) | 2023.10.12 |
| 삼성 SW 기초 문제 (2) (4) | 2023.10.11 |
'C++/SAMSUNG (C++)' Related Articles
more
