반응형
문제링크: https://www.acmicpc.net/problem/14891
14891번: 톱니바퀴
첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴
www.acmicpc.net
전형적인 시뮬레이션 문제입니다. 시뮬레이션 같은 경우에는 구현과 비슷합니다. 대부분 구현방법을 정의해주는 것의 차이라고 하네요.
각 상태별로 상황을 나누어 함수로 작성하였고, 데큐를 사용해서 각 톱니의 값을 저장했습니다.
직관적이지만 낭비적인 제 답안입니다.
#include <iostream>
#include <string>
#include <deque>
using namespace std;
deque <int> arr[4];
int k = 0, a = 0, b = 0;
int result = 0;
void one_c() {//정
if (arr[0][2] != arr[1][6]) { // 반대
if (arr[1][2] != arr[2][6] ) { //정
if (arr[2][2] != arr[3][6] ) {//반대
int temp = arr[3].front(); //반대
arr[3].pop_front();
arr[3].push_back(temp);
}
int temp = arr[2].back(); //정방향
arr[2].pop_back();
arr[2].push_front(temp);
}
int temp = arr[1].front(); //반대
arr[1].pop_front();
arr[1].push_back(temp);
}
int temp = arr[0].back(); //정방향
arr[0].pop_back();
arr[0].push_front(temp);
}
void one_k() {//반
if (arr[0][2] != arr[1][6]) { // 정
if (arr[1][2] != arr[2][6]) { // 반
if (arr[2][2] != arr[3][6]) {//정
int temp = arr[3].back(); //정
arr[3].pop_back();
arr[3].push_front(temp);
}
int temp = arr[2].front(); //반
arr[2].pop_front();
arr[2].push_back(temp);
}
int temp = arr[1].back(); //정
arr[1].pop_back();
arr[1].push_front(temp);
}
int temp = arr[0].front(); //반
arr[0].pop_front();
arr[0].push_back(temp);
}
void two_c() { //정
if (arr[0][2] != arr[1][6]) { //반
int temp = arr[0].front(); //반
arr[0].pop_front();
arr[0].push_back(temp);
}
if (arr[1][2] != arr[2][6]) { //반
if (arr[2][2] != arr[3][6]) {//정
int temp = arr[3].back(); //정
arr[3].pop_back();
arr[3].push_front(temp);
}
int temp = arr[2].front(); //반
arr[2].pop_front();
arr[2].push_back(temp);
}
int temp = arr[1].back(); //정
arr[1].pop_back();
arr[1].push_front(temp);
}
void two_k() { //반
if (arr[0][2] != arr[1][6]) { //정
int temp = arr[0].back(); //정
arr[0].pop_back();
arr[0].push_front(temp);
}
if (arr[1][2] != arr[2][6]) { //정
if (arr[2][2] != arr[3][6]) {//반
int temp = arr[3].front(); //반
arr[3].pop_front();
arr[3].push_back(temp);
}
int temp = arr[2].back(); //정
arr[2].pop_back();
arr[2].push_front(temp);
}
int temp = arr[1].front(); //반
arr[1].pop_front();
arr[1].push_back(temp);
}
void three_c() { //정
if (arr[2][2] != arr[3][6]) { //반
int temp = arr[3].front(); //반
arr[3].pop_front();
arr[3].push_back(temp);
}
if (arr[1][2] != arr[2][6]) { //반
if (arr[0][2] != arr[1][6]) { //정
int temp = arr[0].back(); //정
arr[0].pop_back();
arr[0].push_front(temp);
}
int temp = arr[1].front(); //반
arr[1].pop_front();
arr[1].push_back(temp);
}
int temp = arr[2].back(); //정
arr[2].pop_back();
arr[2].push_front(temp);
}
void three_k() { //반
if (arr[2][2] != arr[3][6]) { //정
int temp = arr[3].back(); //정
arr[3].pop_back();
arr[3].push_front(temp);
}
if (arr[1][2] != arr[2][6]) { //정
if (arr[0][2] != arr[1][6]) { //반
int temp = arr[0].front(); //반
arr[0].pop_front();
arr[0].push_back(temp);
}
int temp = arr[1].back(); //정
arr[1].pop_back();
arr[1].push_front(temp);
}
int temp = arr[2].front(); //반
arr[2].pop_front();
arr[2].push_back(temp);
}
void four_c() { //정
if (arr[2][2] != arr[3][6]) { // 반대
if (arr[1][2] != arr[2][6]) { //정
if (arr[0][2] != arr[1][6]) {//반대
int temp = arr[0].front(); //반대
arr[0].pop_front();
arr[0].push_back(temp);
}
int temp = arr[1].back(); //정방향
arr[1].pop_back();
arr[1].push_front(temp);
}
int temp = arr[2].front(); //반대
arr[2].pop_front();
arr[2].push_back(temp);
}
int temp = arr[3].back(); //정방향
arr[3].pop_back();
arr[3].push_front(temp);
}
void four_k() { //반
if (arr[2][2] != arr[3][6]) { // 정
if (arr[1][2] != arr[2][6]) { //반
if (arr[0][2] != arr[1][6]) {//정
int temp = arr[0].back(); //정
arr[0].pop_back();
arr[0].push_front(temp);
}
int temp = arr[1].front(); //반
arr[1].pop_front();
arr[1].push_back(temp);
}
int temp = arr[2].back(); //정
arr[2].pop_back();
arr[2].push_front(temp);
}
int temp = arr[3].front(); //반
arr[3].pop_front();
arr[3].push_back(temp);
}
int main() {
for (int i = 0; i < 4; i++) {
string num;
cin >> num;
for (int j = 0; j < 8; j++)
arr[i].push_back(num[j]- '0');
}
cin >> k;
while (k--) {
cin >> a >> b;
if (a == 1 && b == 1)
one_c();
else if (a == 1 && b == -1)
one_k();
else if (a == 2 && b == 1)
two_c();
else if (a == 2 && b == -1)
two_k();
else if (a == 3 && b == 1)
three_c();
else if (a == 3 && b == -1)
three_k();
else if (a == 4 && b == 1)
four_c();
else if (a == 4 && b == -1)
four_k();
}
if (arr[0].front() == 1)
result += 1;
if (arr[1].front() == 1)
result += 2;
if (arr[2].front() == 1)
result += 4;
if (arr[3].front() == 1)
result += 8;
cout << result << endl;
}
복붙이 많아서 구현의 큰 어려움없었습니다.
하지만 굳이 8가지의 상황을 나눠서 구현할 필요가 없던 문제입니다.
이렇게 작성하는 것의 단점은 오타를 찾기 힘들다는 것입니다. 코드가 길기때문에 조심하지 않으면 오타나 논리에러를 만들것이고, 테스트케이스를 통과했는데, 해당 에러를 못찾으면 그때부터 지옥의 시작입니다.
그래서
- 시뮬레이션에서는 구현전에 최대한 자세하게 청사진을 만든다.
- 구현 중간중간 수시로 테스트케이스를 만들어 대입해보며, 에러가 없는지 수시로 찾는다.
이 두가지를 지키면서 꼼꼼하게 작성해야합니다.
아래 코드는 다른 분의 좀더 컴팩트한 답안입니다.
#include <cstdio>
using namespace std;
#define S '1'
#define right(int) (int + 2) % 8
#define left(int) (int - 2 + 8) % 8
char list[4][8];
int N, ans = 0;
int pos[4] = { 0, };
void run(int n, int d, bool bl, bool br) {
if (n < 0 || n >= 4) return;
if (n + 1 < 4 && !br)
if (list[n][right(pos[n])] != list[n + 1][left(pos[n + 1])])
run(n + 1, d * -1, true, false);
if (n - 1 >= 0 && !bl)
if (list[n - 1][right(pos[n - 1])] != list[n][left(pos[n])])
run(n - 1, d * -1, false, true);
pos[n] = (pos[n] + (d * -1) + 8) % 8;
}
int main() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 8; j++)
scanf(" %c", &list[i][j]);
}
scanf("%d", &N);
for (int i = 0; i < N; i++) {
int n, d;
scanf("%d %d", &n, &d);
run(n - 1, d, false, false);
}
for (int i = 0; i < 4; i++)
if (list[i][pos[i]] == S)
ans += 1 << i;
printf("%d\n", ans);
return 0;
}
톱니바퀴이동읠 8가지유형을 묶어버리고, 재귀함수를 사용함으로써 컴팩트하게 구현했습니다.
밑에는 조금 덜 컴팩트하지만, 직관적인 코드입니다.
#include <iostream>
#include <string>
#include <deque>
#include <queue>
#include <cmath>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
deque<int> dq[5];
for (int i = 1; i < 5; i++)
{
string s;
cin >> s;
for(int j=0; j<s.length(); j++)
dq[i].push_back(s[j] - '0');
}
int K;
cin >> K;
for (int i = 0; i < K; i++)
{
int num, dir;
cin >> num >> dir;
int idx = num;
int tempDir = dir;
queue<pair<int, int>> q;
q.push({ idx, tempDir });
//check right
while (1)
{
if (idx == 4)
break;
idx++;
tempDir *= -1;
if (dq[idx - 1][2] != dq[idx][6])
q.push({ idx, tempDir });
else
break;
}
idx = num;
tempDir = dir;
//check left
while (1)
{
if (idx == 1)
break;
idx--;
tempDir *= -1;
if (dq[idx + 1][6] != dq[idx][2])
q.push({ idx, tempDir });
else
break;
}
//rotate the magnet
while (!q.empty())
{
int cur = q.front().first;
int rotate = q.front().second;
q.pop();
//clockwise
if (rotate == 1)
{
int temp = dq[cur].back();
dq[cur].pop_back();
dq[cur].push_front(temp);
}
//anti clockwise
else
{
int temp = dq[cur].front();
dq[cur].pop_front();
dq[cur].push_back(temp);
}
}
}
int result = 0;
for (int i = 1; i < 5; i++)
if (dq[i].front() == 1)
result += (int)pow(2, i - 1);
cout << result << "\n";
return 0;
}
출처: https://jaimemin.tistory.com/1174
백준 14891번 톱니바퀴
문제 링크입니다: https://www.acmicpc.net/problem/14891 동기의 요청으로 풀어본 문제인데 꽤나 재밌는 문제였습니다. 저는 덱을 이용하여 시뮬레이션을 돌려 풀었는데 조세퍼스 문제처럼 인덱스를 모듈러 연산..
jaimemin.tistory.com
코드의 답은 없습니다.
선택은 여러분의 몫! ㅎㅎ
반응형
'알고리즘 > 시뮬레이션' 카테고리의 다른 글
| [백준] 16236-아기 상어(C++) (0) | 2020.06.14 |
|---|---|
| [백준] 11559-Puyo Puyo(C++) (0) | 2020.05.03 |
| [백준] 14500-테트로미노(C++) (0) | 2020.04.14 |
| [백준] 1021-회전하는 큐(C++) (0) | 2020.04.02 |
| [백준] 14499-주사위 굴리기 (0) | 2020.01.29 |