시뮬레이션
문제에 나와있는대로 무언가를 하는 알고리즘
시뮬레이션에서는 문제에서 어떻게하라고 나와있다. 그래서 시뮬레이션 문제는 그대로 구현을 해주면된다.
문제
16935 배열 돌리기3
크기가 NxM 배열이 있을때 문제에 나와있는 배열 돌리기 연산을 구현하는 문제배열이 있을때 문제에 나와있는 배열 돌리기 연산을 구현하는 문제
구슬 탈출 2
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 문제 이때 파란구슬도 있기 때문에 파란구슬은 빠지면 안된다.
NxM 1x1 크기의 칸이 있어서 빈칸, 벽, 구멍, 빨간, 파랑
보드를 기울여서 구슬을 꺼내야 한다. 10번 이내에 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
그래서 기울이는 것을 10번만 시도해보면 된다. (4^10개의 경우의 수가 존재한다.)
- 기울일 수 있는 모든 방법을 만들고(브루트포스) -> 문제에 나와있는 대로 시뮬레이션
14503 로봇 청소기
로봇청소기를 작동시켜서 총 몇 개의 칸을 청소하는지 구하는 문제
0 은 청소하지 않은 칸
1 은 벽
2 는 청소한 칸이라고 하자
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, m, s, w, h, nx, ny, k;
ll n;
int map[51][51];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
int r, c, dir;
cin >> n >> m;
cin >> r >> c >> dir;
for (i = 0; i < n; ++i)
{
for (j = 0; j < m; ++j)
{
cin >> map[i][j];
}
}
while (true)
{
if (map[r][c] == 0) map[r][c] = 2;
if (map[r - 1][c] != 0 && map[r][c + 1] != 0 && map[r + 1][c] != 0 && map[r][c - 1] != 0)
{
if (map[r - dx[dir]][c - dy[dir]] == 1)
break;
else
{
r -= dx[dir];
c -= dy[dir];
}
}
else
{
dir = (dir + 3) % 4;
if (map[r + dx[dir]][c + dy[dir]] == 0)
{
r += dx[dir];
c += dy[dir];
}
}
}
for (i = 0; i < n; ++i)
{
for (j = 0; j < m; ++j)
{
if (map[i][j] == 2) ans += 1;
}
}
cout << ans << '\n';
}14890 경사로
지도의 한 줄을 지나갈 수 있는지 검사하는 문제로 높이가 같아야만 지나갈 수 있다.
행, 열 단위로 움직이면서 모든 가로, 세로 줄을 적어도 한 번씩은 검사해주어야 한다.
경사로를 놓을 수 있는데 이때에도 높이 차이는 반드시 1이어야 하고, 최대 놓을 수 있는 길이가 정해져 있다. 그리고 중복해서도 안된다.
경사로를 놓을 수 있는 방향이 두개이기 때문에 잘 처리해주면 될거라고 생각한다.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
//int ans, i, j, m, s, w, h, nx, ny, k;
//ll n;
bool go(vector<int> &d, int l)
{
int n = d.size();
vector<bool> chk(n, false);
for (int i = 1; i < n; ++i)
{
int diff = abs(d[i] - d[i - 1]);
if (diff == 0) continue;
if (diff != 1) return (false);
//이전
if (d[i] > d[i - 1] )
{
for (int j = 1; j <= l; ++j)
{
if (i - j < 0) return (false);
if (chk[i - j]) return (false);
if (d[i - 1] != d[i - j]) return (false);
chk[i - j] = true;
}
}
else
{
//이후
for (int j = 0; j < l; ++j)
{
if (i + j >= n) return (false);
if (chk[i + j]) return (false);
if (d[i] != d[i + j]) return (false);
chk[i + j] = true;
}
}
}
return (true);
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, l, ans = 0;
cin >> n >> l;
vector<vector<int>> map(n, vector<int> (n));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> map[i][j];
}
}
//가로방향 검사
for (int i = 0; i < n; ++i)
{
vector<int> d;
for (int j = 0; j < n; ++j)
{
d.push_back(map[i][j]);
}
if (go(d, l)) ans += 1;
}
//세로방향 검사
for (int j = 0; j < n; ++j)
{
vector<int> d;
for (int i = 0; i < n; ++i)
{
d.push_back(map[i][j]);
}
if (go(d, l)) ans += 1;
}
cout << ans << '\n';
}15685 드래곤 커브
- 시작점 / 2. 방향 / 3. 세대
세대별로 끝점을 기준으로 90도 시계방향 회전한 것을 갖다 붙이고 최종적으로 네 꼭지점에 드래곤 커브가 이는 정사각형의 갯수를 구하는 문제이다.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
//int ans, i, j, m, s, w, h, nx, ny, k;
//ll n;
int c[101][101];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
vector<int> curve(int dir, int gen)
{
//0세대
vector<int> ans = { dir };
//1세대부터 gen까지
for (int i = 1; i <= gen; ++i)
{
vector<int> tmp(ans);
reverse(tmp.begin(), tmp.end());
for (int &i : tmp)
{
i = (i + 1) % 4;
}
ans.insert(ans.end(), tmp.begin(), tmp.end());
}
return (ans);
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
while (n--)
{
int x, y, d, g;
cin >> x >> y >> d >> g;
vector<int> dir = curve(d, g);
c[y][x] = true;
for (int i : dir)
{
x += dx[i];
y += dy[i];
c[y][x] = true;
}
}
int ans = 0;
for (int i = 0; i <= 99; ++i)
{
for (int j = 0; j <= 99; ++j)
{
if (c[i][j] && c[i + 1][j] && c[i][j + 1] && c[i + 1][j + 1])
ans++;
}
}
cout << ans << '\n';
return (0);
}14891 주사위 굴리기
위에서 나온것은 시뮬레이션 지도 유형이지만 여기에서 나오는건 돌리기 유형이다. 도구유형은 그래서 데이터를 어떻게 저장하고 어떻게 이동시킬지가 중요한 문제이다.
주사위 굴리기와 같은경우 명령어대로 움직이면서 지도와 주사위의 값을 바꾸고 동시에 주사위 가장 위쪽 숫자를 출력하는 것이 중요한 문제이다.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
//int ans, i, j, m, s, w, h, nx, ny, k;
//ll n;
int map[20][20];
int dice[7];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, x, y, k;
cin >> n >> m >> x >> y >> k;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> map[i][j];
}
}
int ord;
while (k--)
{
cin >> ord;
ord -= 1;
int nx = x + dx[ord];
int ny = y + dy[ord];
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
continue;
//east
if (ord == 0)
{
int temp = dice[1];
dice[1] = dice[4];
dice[4] = dice[6];
dice[6] = dice[3];
dice[3] = temp;
}
//west
else if (ord == 1)
{
int temp = dice[1];
dice[1] = dice[3];
dice[3] = dice[6];
dice[6] = dice[4];
dice[4] = temp;
}
//north
else if (ord == 2)
{
int temp = dice[1];
dice[1] = dice[5];
dice[5] = dice[6];
dice[6] = dice[2];
dice[2] = temp;
}
//south
else
{
int temp = dice[1];
dice[1] = dice[2];
dice[2] = dice[6];
dice[6] = dice[5];
dice[5] = temp;
}
x = nx;
y = ny;
if (map[x][y] == 0)
{
map[x][y] = dice[6];
}
else
{
dice[6] = map[x][y];
map[x][y] = 0;
}
cout << dice[1] << '\n';
}
}14891 톱니바퀴
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int main(void) {
freopen("input.txt", "r", stdin);
//ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
vector<vector<int>> gear(4, vector<int>(8, 0));
for (int i = 0; i < 4; ++i)
{
for (int j = 0; j < 8; ++j)
{
scanf("%1d", &gear[i][j]);
}
}
int t;
cin >> t;
while (t--)
{
int num, dir;
int chk[4] = { 0 };
cin >> num >> dir;
num -= 1;
chk[num] = dir;
//왼쪽 기어들 확인
for (int i = 1; num - i >= 0; ++i)
{
if (gear[num - i][2] != gear[num - i + 1][6])
chk[num - i] = -chk[num - i + 1];
else
break;
}
//오른쪽 기어들 확인
for (int i = 1; num + i < 4; ++i)
{
if (gear[num + i][6] != gear[num + i - 1][2])
chk[num + i] = -chk[num + i - 1];
else
break;
}
for (int i = 0; i < 4; ++i)
{
if (chk[i] == 1)
rotate(gear[i].rbegin(), gear[i].rbegin() + 1, gear[i].rend());
else if (chk[i] == -1)
rotate(gear[i].begin(), gear[i].begin() + 1, gear[i].end());
}
}
int ans = 0;
for (int i = 0; i < 4; ++i)
{
if (gear[i][0] == 1)
{
ans |= (1 << i);
}
}
cout << ans << '\n';
}20055 컨베이어 벨트 위의 로봇
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> c(n * 2);
for (int i = 0; i < 2 * n; ++i)
{
cin >> c[i];
}
int cnt = 0;
vector<bool> box(n * 2,false);
for (int t = 1; ; t++)
{
//1. 벨트가 한 칸 회전한다.
rotate(c.rbegin(), c.rbegin() + 1, c.rend());
rotate(box.rbegin(), box.rbegin() + 1, box.rend());
//가장 끝칸에 있는 박스는 내린다.
if (box[n - 1])
{
box[n - 1] = false;
}
//2. 이동할 수 있는지 확인한다.
for (int i = n - 2; i >= 0; --i) {
if (box[i] == true && !box[i + 1] && c[i + 1] > 0)
{
box[i + 1] = true;
box[i] = false;
c[i + 1] -= 1;
if (c[i + 1] == 0) cnt++;
}
}
if (box[n - 1])
{
box[n - 1] = false;
}
//3. 박스 올리기
if (box[0] == false && c[0] > 0)
{
box[0] = true;
c[0] -= 1;
if (c[0] == 0) cnt++;
}
//4. 내구도가 0인 칸의 개수가 K개 이상이면 종료
if (cnt >= k)
{
cout << t << '\n';
break;
}
}
}16234 인구 이동
신촌거지출신개발자(시리즈 부분에 목차가 나옵니다.)