굥뷰를 햡시댜
[BOJ-14891] 톱니바퀴 본문
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
풀이 시간 : 2h
문제를 읽고 시뮬레이션 문제라는 것이 처음부터 직감이 왔다. 이런 류의 시뮬레이션 문제 같은 경우에는 하드코딩하면 따로 생각하지 않고도 답을 구할 수 있다.
회전횟수 k도 최대 100회밖에 회전하지 않기 때문에 최대 회전횟수가 4*100 = 400을 넘지 않아서 하드코딩해도 시간복잡도상 문제는 전혀없다.
정답률이 높은 이유가 있는 문제이다.
나같은 경우도 따로 생각하지 않고 하드코딩한 케이스로 좀 더 똑똑한 사람이 구현한 코드를 한번쯤 참고해봐야겠다.
-풀이방법
1. 문제의 입력을 받는다.
2. k를 입력 받고 k번 반복을 돌린다.
3. 입력받은 톱니바퀴의 시작 번호와 방향에 따라 다른 톱니바퀴들의 회전도 결정되기 때문에 k번 반복하는 반복문 안에 입력받은 톱니바퀴의 번호별로 경우의 수를 나눠준다.
4. 각 경우마다 시계방향, 반시계방향마다 다른 톱니바퀴에 영향을 주기 때문에 다시 한 번 경우의 수를 나눠준다.
5. 그 다음으로는 생각을 조금 한 뒤 각 경우마다 돌아가는 톱니바퀴를 생각만해주면 된다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
int circle1[8];
int circle2[8];
int circle3[8];
int circle4[8];
int k;
int number, direction;
void rotation(int n, int dir) {
if (n == 1) {
if (dir == -1) {
int copy[8] = { 0, };
copy[7] = circle1[0];
copy[0] = circle1[1];
copy[1] = circle1[2];
copy[2] = circle1[3];
copy[3] = circle1[4];
copy[4] = circle1[5];
copy[5] = circle1[6];
copy[6] = circle1[7];
for (int i = 0; i < 8; i++) {
circle1[i] = copy[i];
}
}
else if (dir == 1) {
int copy[8] = { 0, };
copy[1] = circle1[0];
copy[2] = circle1[1];
copy[3] = circle1[2];
copy[4] = circle1[3];
copy[5] = circle1[4];
copy[6] = circle1[5];
copy[7] = circle1[6];
copy[0] = circle1[7];
for (int i = 0; i < 8; i++) {
circle1[i] = copy[i];
}
}
}
else if (n == 2) {
if (dir == -1) {
int copy[8] = { 0, };
copy[7] = circle2[0];
copy[0] = circle2[1];
copy[1] = circle2[2];
copy[2] = circle2[3];
copy[3] = circle2[4];
copy[4] = circle2[5];
copy[5] = circle2[6];
copy[6] = circle2[7];
for (int i = 0; i < 8; i++) {
circle2[i] = copy[i];
}
}
else if (dir == 1) {
int copy[8] = { 0, };
copy[1] = circle2[0];
copy[2] = circle2[1];
copy[3] = circle2[2];
copy[4] = circle2[3];
copy[5] = circle2[4];
copy[6] = circle2[5];
copy[7] = circle2[6];
copy[0] = circle2[7];
for (int i = 0; i < 8; i++) {
circle2[i] = copy[i];
}
}
}
else if (n == 3) {
if (dir == -1) {
int copy[8] = { 0, };
copy[7] = circle3[0];
copy[0] = circle3[1];
copy[1] = circle3[2];
copy[2] = circle3[3];
copy[3] = circle3[4];
copy[4] = circle3[5];
copy[5] = circle3[6];
copy[6] = circle3[7];
for (int i = 0; i < 8; i++) {
circle3[i] = copy[i];
}
}
else if (dir == 1) {
int copy[8] = { 0, };
copy[1] = circle3[0];
copy[2] = circle3[1];
copy[3] = circle3[2];
copy[4] = circle3[3];
copy[5] = circle3[4];
copy[6] = circle3[5];
copy[7] = circle3[6];
copy[0] = circle3[7];
for (int i = 0; i < 8; i++) {
circle3[i] = copy[i];
}
}
}
else if (n == 4) {
if (dir == -1) {
int copy[8] = { 0, };
copy[7] = circle4[0];
copy[0] = circle4[1];
copy[1] = circle4[2];
copy[2] = circle4[3];
copy[3] = circle4[4];
copy[4] = circle4[5];
copy[5] = circle4[6];
copy[6] = circle4[7];
for (int i = 0; i < 8; i++) {
circle4[i] = copy[i];
}
}
else if (dir == 1) {
int copy[8] = { 0, };
copy[1] = circle4[0];
copy[2] = circle4[1];
copy[3] = circle4[2];
copy[4] = circle4[3];
copy[5] = circle4[4];
copy[6] = circle4[5];
copy[7] = circle4[6];
copy[0] = circle4[7];
for (int i = 0; i < 8; i++) {
circle4[i] = copy[i];
}
}
}
}
//s -> 1, n -> 0
int main(void) {
for (int i = 0; i < 4; i++) {
string s;
cin >> s;
for (int j = 0; j < s.length(); j++) {
if (i == 0) {
circle1[j] = s[j] - 48;
}
else if (i == 1) {
circle2[j] = s[j] - 48;
}
else if (i == 2) {
circle3[j] = s[j] - 48;
}
else if (i == 3) {
circle4[j] = s[j] - 48;
}
}
}
scanf("%d", &k);
for (int i = 0; i < k; i++) {
scanf("%d %d", &number, &direction);
if (number == 1) {
if (direction == -1) {
if (circle1[2] != circle2[6]) {
if (circle2[2] != circle3[6]) {
if (circle3[2] != circle4[6]) {
rotation(4, 1);
}
rotation(3, -1);
}
rotation(2, 1);
}
rotation(1, -1);
}
else if (direction == 1) {
if (circle1[2] != circle2[6]) {
if (circle2[2] != circle3[6]) {
if (circle3[2] != circle4[6]) {
rotation(4, -1);
}
rotation(3, 1);
}
rotation(2, -1);
}
rotation(1, 1);
}
}
else if (number == 2) {
if (direction == -1) {
if (circle2[2] != circle3[6]) {
if (circle3[2] != circle4[6]) {
rotation(4, -1);
}
rotation(3, 1);
}
if (circle2[6] != circle1[2]) {
rotation(1, 1);
}
rotation(2, -1);
}
else if (direction == 1) {
if (circle2[2] != circle3[6]) {
if (circle3[2] != circle4[6]) {
rotation(4, 1);
}
rotation(3, -1);
}
if (circle2[6] != circle1[2]) {
rotation(1, -1);
}
rotation(2, 1);
}
}
else if (number == 3) {
if (direction == -1) {
if (circle3[6] != circle2[2]) {
if (circle2[6] != circle1[2]) {
rotation(1, -1);
}
rotation(2, 1);
}
if (circle3[2] != circle4[6]) {
rotation(4, 1);
}
rotation(3, -1);
}
else if (direction == 1) {
if (circle3[6] != circle2[2]) {
if (circle2[6] != circle1[2]) {
rotation(1, 1);
}
rotation(2, -1);
}
if (circle3[2] != circle4[6]) {
rotation(4, -1);
}
rotation(3, 1);
}
}
else if (number == 4) {
if (direction == -1) {
if (circle4[6] != circle3[2]) {
if (circle3[6] != circle2[2]) {
if (circle2[6] != circle1[2]) {
rotation(1, 1);
}
rotation(2, -1);
}
rotation(3, 1);
}
rotation(4, -1);
}
else if (direction == 1) {
if (circle4[6] != circle3[2]) {
if (circle3[6] != circle2[2]) {
if (circle2[6] != circle1[2]) {
rotation(1, -1);
}
rotation(2, 1);
}
rotation(3, -1);
}
rotation(4, 1);
}
}
}
int res = 0;
if (circle1[0] == 1) res += 1;
if (circle2[0] == 1) res += 2;
if (circle3[0] == 1) res += 4;
if (circle4[0] == 1) res += 8;
printf("%d\n", res);
getchar();
getchar();
return 0;
}'알고리즘 문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글
| [BOJ-17281] 야구 (0) | 2019.08.16 |
|---|---|
| [BOJ-13458] 시험감독 (0) | 2019.08.13 |
| [BOJ-15686] 치킨배달 (0) | 2019.07.26 |
| [BOJ-14503] 로봇청소기 (0) | 2019.07.26 |
| [BOJ-17070] 파이프 옮기기1 (0) | 2019.07.19 |
Comments