Notice
Recent Posts
천천히 빛나는
삼성 SW 기출 문제 (1) 본문
본 포스팅에서는 [이차원 배열과 연산 , 컨베이어 벨트 위의 로봇, 마법사 상어와 파이어볼, 마법사 상어와 토네이도]를 다룹니다.
17140. (이차원 배열과 연산) 배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int c, r, k;
int A[101][101];
int cRnum;
int cCnum;
int result;
void Calculation() {
if (A[r][c] == k) {
cout << result;
return;
}
if (result == 100) {
cout << -1;
return;
}
vector<int> size;
if (cRnum >= cCnum) {
for (int i = 1; i <= cRnum; i++)
{
// 개수 측정
int cnt[101] = { 0, };
vector<pair<int, int>> V;
for (int j = 1; j <= cCnum; j++)
{
cnt[A[i][j]]++; // cnt의 idx에 해당하는 숫자가 몇개인지
}
for (int j = 1; j < 101; j++)
{
if (cnt[j] != 0) {
// 등장횟수가 커지는 순으로
V.push_back({ cnt[j], j });
}
}
sort(V.begin(), V.end());
for (int j = 1; j <= cCnum; j++) {
A[i][j] = 0;
}
int idx = 1;
for (int j = 0; j < V.size(); j ++)
{
A[i][idx++] = V[j].second;
A[i][idx++] = V[j].first;
}
size.push_back(idx - 1);
}
sort(size.begin(), size.end());
cCnum = size.back();
}
else {
for (int j = 1; j <= cCnum; j++)
{
// 개수 측정
int cnt[101] = { 0, };
vector<pair<int, int>> V;
for (int i = 1; i <= cRnum; i++)
{
cnt[A[i][j]]++; // cnt의 idx에 해당하는 숫자가 몇개인지
}
for (int i = 1; i < 101; i++)
{
if (cnt[i] != 0) {
V.push_back({ cnt[i], i });
}
}
sort(V.begin(), V.end());
for (int i = 1; i <= cRnum; i++) {
A[i][j] = 0;
}
int idx = 1;
for (int i = 0; i < V.size(); i++)
{
A[idx++][j] = V[i].second;
A[idx++][j] = V[i].first;
}
size.push_back(idx - 1);
}
sort(size.begin(), size.end());
cRnum = size.back();
}
result++;
Calculation();
}
int main() {
cin >> r >> c >> k;
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
cin >> A[i][j];
}
}
cRnum = 3;
cCnum = 3;
Calculation();
return 0;
}입력하자마자 r, c에 k가 있는 경우를 생각해서 맨 위쪽에 빼주어야 한다.
1) 등장횟수를 cnt 배열에 저장
예를 들어 1이 3번 등장했으면 cnt[1]=3이 된다.
2) 등장횟수가 1 이상인 값들만 벡터 V에 저장
3) sort 함수로 V를 정렬 => 등장횟수의 오름차순으로 정렬된다. 등장횟수가 같으면 그 다음 값인 수의 오름차순으로 정렬된다.
4) 기존 저장되어있던 값을 모두 0으로 바꾸고 V에 저장된 값 순서대로 삽입
0으로 바꾸는 이유는 max 값이 얼마가 될지 아직 모르기 때문이다
5) 저장을 하면서 마지막으로 저장된 index 값을 벡터 size에 저장한다
6) size를 오름차순하여 size의 max 값을 구한다
7) size의 max 값을 해당 행 또는 열의 사이즈로 업데이트한다
20055. (컨베이어 벨트 위의 로봇) 종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int n, k;
deque<int> A; // 내구성
deque<bool> conveyer; // 존재하는지
int step = 1;
void rotate(){
while (1) {
// 1. 회전
conveyer.push_front(conveyer.back());
conveyer.pop_back();
A.push_front(A.back());
A.pop_back();
conveyer[n - 1] = false; // 누구 있으면 내림
// 2. 이동
// 가장 먼저 올라간 로봇 = n이랑 가까운 로봇
for (int i = n - 2; i >= 0; i--)
{
// 다음칸에 누가 없고, 내구성이 0보다 클때
if (!conveyer[i + 1] && A[i + 1] > 0 && conveyer[i]) {
conveyer[i] = false; // 이동
conveyer[i + 1] = true;
A[i + 1]--; // 내구성 감소
}
}
conveyer[n - 1] = false; // 누구 있으면 내림
// 3. 로봇 올리기
if (A[0] > 0) { // 첫째칸에 내구성 있음
conveyer[0] = true;
A[0]--;
}
int cnt = 0;
for (int i = 0; i < 2 * n; i++) {
if (A[i] == 0)
cnt++;
}
if (cnt >= k) {
cout << step;
return;
}
step++;
}
}
int main() {
cin >> n >> k;
for (int i = 0; i < 2 * n; i++)
{
int x;
cin >> x;
A.push_back(x);
conveyer.push_back(false);
}
rotate();
}나는 queue를 이용해서 풀었는데, 알고보니 deque을 이용하면 훨씬 편하게 풀 수 있었다. Deque는 que랑 다르게 index 접근이 가능했다!! push를 통해 추가가 가능하고 원하는 위치에 insert를 통해서 삽입도 가능하다.
// dq에 3, 1이 들어있던 생태라면
cout<<dq[0]; // 3 출력
dq.insert(dq.begin()+1, 2); // 3, 2, 1이 된다 (원하는 곳의 위치를 넣기)
dq.erase(dq.begin()); // 2, 1이 된다인덱스 접근이 가능한지 몰랐어서 좀 충격이었다. 또 주소도 접근이 가능하다. 벡터인데 앞뒤가 뚫인 벡터로 생각하면 될 것 같다. 회전은 deque로 구현하는게 정말 편하다.
20056. (마법사 상어와 파이어볼) 마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.
#include <iostream>
#include <vector>
using namespace std;
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
struct fireball
{
int r;
int c;
int m;
int s;
int d;
};
int N, M, K;
vector<fireball> map[51][51];
vector<fireball> fireBalls;
void game() {
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
map[i][j].clear();
}
}
for (int i = 0; i < fireBalls.size(); i++)
{
int r = fireBalls[i].r;
int c = fireBalls[i].c;
int m = fireBalls[i].m;
int s = fireBalls[i].s;
int d = fireBalls[i].d;
int speed = s % N;
int nx = r + dx[d] * speed;
int ny = c + dy[d] * speed;
if (nx > N)
nx -= N;
else if (nx < 1)
nx += N;
if (ny > N)
ny -= N;
else if (ny < 1)
ny += N;
map[nx][ny].push_back({ nx, ny, m, s, d });
fireBalls[i].r = nx;
fireBalls[i].c = ny;
}
vector<fireball>temp;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (map[i][j].size() == 0)
continue;
if (map[i][j].size() == 1){
temp.push_back(map[i][j][0]);
continue;
}
int mSum = 0;
int sSum = 0;
bool even = true;
bool odd = true;
for (int k = 0; k < map[i][j].size(); k++)
{
mSum += map[i][j][k].m;
sSum += map[i][j][k].s;
if (map[i][j][k].d % 2 == 0)
odd = false;
else
even = false;
}
mSum /= 5;
sSum /= map[i][j].size();
if (mSum == 0)
continue;
if (even == 1 || odd == 1) {
for (int k = 0; k < 4; k++)
{
temp.push_back({i, j, mSum, sSum, k*2});
}
}
else {
for (int k = 0; k < 4; k++)
{
temp.push_back({ i, j, mSum, sSum, k * 2 +1 });
}
}
}
}
fireBalls = temp;
}
int main() {
cin >> N >> M >> K;
while (M--) {
int r, c, m, s, d;
cin >> r >> c >> m >> s >> d;
fireBalls.push_back({ r, c , m, s, d });
map[r][c].push_back({ r, c, m, s, d });
}
for (int i = 0; i < K; i++)
{
game();
}
int result = 0;
for (int i = 0; i < fireBalls.size(); i++)
{
result += fireBalls[i].m;
}
cout << result;
}map은 단순히 하나의 좌표에 몇개 도착할 예정인지를 저장하는 벡터이다. 즉 2번인 파이어볼 이동이 끝난다면, 그 이후에 map을 업데이트 해줄 이유가 없다는 것이다. 항상 이동 전에는 map 벡터가 초기화가 된다. (도착할 곳을 정하지 않았으니까)
struct을 이용해서 구현하였으며 %N을 해준 이유는 N번 이동하면 원래 자리로 돌아오기 때문이다.
temp 벡터를 사용해서 합쳐진 벡터까지 반영된 temp 벡터를 만들었으며 (합쳐지기 전은 fireBalls 벡터에 저장되어있음) temp 벡터가 완성이 되면 fireBalls을 temp로 덮어쓴다.
20057. (마법사 상어와 토네이도) 토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.
#include<iostream>
using namespace std;
int N;
int A[500][500];
bool visited[500][500];
int r, c;
int d; // 현재 방향
// 1 1 2 2 3 3 4 4
// 좌 하 우 상
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
int tdx[4][10] = {
{-1, 1, -1, 1, -1, 1, -2, 2, 0, 0},
{1, 1, 0, 0, -1, -1, 0, 0, 2, 1},
{-1, 1, -1, 1, -1, 1, -2, 2, 0, 0},
{ -1, -1, 0, 0, 1, 1, 0, 0, -2 , -1},
};
int tdy[4][10] = {
{-1, -1, 0, 0, 1, 1, 0, 0, -2, -1},
{-1, 1, -1, 1, -1, 1, -2, 2, 0, 0},
{1, 1, 0, 0, -1, -1, 0, 0, 2 ,1},
{-1, 1, -1, 1, -1, 1, -2, 2, 0, 0}
};
double percent[] = {0.1, 0.1, 0.07, 0.07, 0.01, 0.01, 0.02, 0.02, 0.05};
int out = 0;
void changeDirection() {
int nextD = (d + 1) % 4;
int nx = r + dx[nextD];
int ny = c + dy[nextD];
// 범위를 벗어나는 이동방향
if (nx < 0 || nx >= N || ny < 0 || ny >= N)
return;
// 이미 지나갔음
if (visited[nx][ny] == 1)
return;
d = nextD;
}
void tornadoShark() {
while (1) {
// 방문 완료
visited[r][c] = 1;
// 0, 0에 도달하면 끝내기
if (r == 0 && c == 0) {
cout << out;
break;
}
// 한칸 이동
int nx = r + dx[d];
int ny = c + dy[d];
int give = 0;
for (int i = 0; i < 10; i++)
{
// 이동한 칸을 기준으로 계산
int tnx = nx + tdx[d][i];
int tny = ny + tdy[d][i];
if (tnx < 0 || tnx >= N || tny < 0 || tny >= N) {
if (i < 9) {
out += int(A[nx][ny] * percent[i]);
give += int(A[nx][ny] * percent[i]);
}
else {
out += A[nx][ny] - give;
}
continue;
}
if (i < 9) {
// 해당 퍼센트만큼 더하기
A[tnx][tny] += int(A[nx][ny] * percent[i]);
give += int(A[nx][ny] * percent[i]);
}
else {
A[tnx][tny] += A[nx][ny] - give;
}
}
A[nx][ny] = 0;
r = nx;
c = ny;
// 다음 방향으로 바꿀 수 있다면 바꿈
changeDirection();
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> A[i][j];
}
}
r = N / 2;
c = N / 2;
tornadoShark();
return 0;
}난 visited 함수를 사용해서 구현했으나 보통 사람들은 2번씩 움직이면 방향을 바꾸도록 했다. 그렇게 하면 이중 for문으로 구현하면 된다. 난 그냥 visited으로 구현했다.
'C++ > SAMSUNG (C++)' 카테고리의 다른 글
| 삼성 SW 기출 문제 (3) (0) | 2023.10.14 |
|---|---|
| 삼성 SW 기출 문제 (2) (1) | 2023.10.13 |
| 삼성 SW 기초 문제 (2) (4) | 2023.10.11 |
| 삼성 SW 기초 문제 (1) (1) | 2023.10.10 |
'C++/SAMSUNG (C++)' Related Articles
more
