[백준 14891번] 톱니바퀴 C++
[14891번 톱니바퀴]
https://www.acmicpc.net/problem/14891
복잡한 알고리즘 없이 정직하게 조건대로 구현하는 문제였다. 코드 길이가 (헤더 제외) 약 2000byte 정도 나왔는데, 맞힌 사람 중에느 700 byte로 구현한 사람도 있었다. 좀 더 정진해야겠다.
풀이 방법
1.
톱니 바퀴를 2차원 배열로 1번~4번까지 모두 입력받는다.
움직이기 시작하는 톱니바퀴 번호와 방향을 K열을 가진 2차원 배열로 입력받는다.
2.
우선 spin 메서드를 구현한다. c++의 rotate라는 메서드를 이용했다. 방향이 -1일 때, 1차원 배열에서 보면 왼쪽으로 한 칸씩 이동하는 것과 같다. 반대로 1일 때는 오른쪽으로 한 칸씩 이동하는 것과 같다.
3.
checkEffect 메서드를 구현한다. 인접한 톱니바퀴 중 왼쪽에 위치한 톱니바퀴를 첫 번째 인자에, 오른쪽에 위치한 톱니바퀴를 두 번째 인자에 넣어주는 메서드를 구현한다. 왼쪽 톱니바퀴의 3번째 이빨과 오른쪽 톱니바퀴의 7번째 이빨의 값이 다르면 true를 반환한다.
4.
rippleEffect 메서드를 구현한다. switch문을 사용하여 1번 톱니바퀴에서 회전이 시작된다면 일어날 수 있는 경우의 수만큼 if문을 활용하여 각각의 결과를 구현한다.
여기서 주의할 점은 파급효과가 가장 멀리까지 뻗치고 돌아오면서, 멀리 있는 톱니바퀴부터 방향에 맞게 회전시켜 줘야한다(파급효과의 연속적 비교를 위해 이전의 톱니바퀴를 미리 회전시키면 안 된다).
5.
score 메서드는 마지막으로 점수를 계산해주는 메서드이다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility> // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;
int ans = 0;
int cogs[5][9];
int k;
int rotation[101][2];
bool checkEffect(int left, int right) {
return cogs[left][3] != cogs[right][7];
}
int spin(int r, int dir) {
if(dir == -1) { // counter-clockwise
rotate(cogs[r]+1, cogs[r] + 2 , cogs[r] + 9);
} else if(dir == 1) { // clockwise
rotate(cogs[r]+1, cogs[r] + 8, cogs[r] + 9);
}
return 0;
}
void rippleEffect(int start, int d) { // number of cogs
switch(start) {
case 1:
if(checkEffect(1,2)) { // first arg idx 3 vs. second arg idx 7
if(checkEffect(2,3)) {
if(checkEffect(3,4)) {
spin(4,-d);
}
spin(3,d);
}
spin(2,-d);
}
spin(1,d);
break;
case 2:
if(checkEffect(1,2) || checkEffect(2,3)) {
if(checkEffect(1,2) && checkEffect(2,3)) {
if(checkEffect(3,4)) {
spin(4,d);
}
spin(3,-d);
spin(1,-d);
} else if(checkEffect(1,2)) {
spin(1,-d);
} else if(checkEffect(2,3)) {
if(checkEffect(3,4)) {
spin(4,d);
}
spin(3,-d);
}
}
spin(2,d);
break;
case 3:
if(checkEffect(2,3) || checkEffect(3,4)) {
if(checkEffect(2,3) && checkEffect(3,4)) {
if(checkEffect(1,2)) {
spin(1,d);
}
spin(2,-d);
spin(4,-d);
} else if(checkEffect(2,3)) {
if(checkEffect(1,2)) {
spin(1,d);
}
spin(2,-d);
} else if(checkEffect(3,4)) {
spin(4,-d);
}
}
spin(3,d);
break;
case 4:
if(checkEffect(3,4)) {
if(checkEffect(2,3)) {
if(checkEffect(1,2)) {
spin(1,-d);
}
spin(2,d);
}
spin(3,-d);
}
spin(4,d);
break;
}
return;
}
void score() {
for(int i=1;i<=4;++i) {
switch(i) {
case 1:
if(cogs[i][1] == 1) {
ans += 1;
}
break;
case 2:
if(cogs[i][1] == 1) {
ans += 2;
}
break;
case 3:
if(cogs[i][1] == 1) {
ans += 4;
}
break;
case 4:
if(cogs[i][1] == 1) {
ans += 8;
}
break;
}
}
return;
}
void sol() {
for(int i=1;i<=k;++i) {
rippleEffect(rotation[i][0], rotation[i][1]);
}
score();
return;
}
int main(void) {
// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
for(int i=1;i<=4;++i) {
for(int j=1;j<=8;++j) {
scanf("%1d", &cogs[i][j]);
}
}
scanf("%d", &k);
for(int i=1;i<=k;++i) {
scanf("%d %d", &rotation[i][0], &rotation[i][1]);
}
sol();
printf("%d\n", ans);
return 0;
}
주의할 점
cout,cin과 scanf(), printf()를 같이 사용하게 되면 백준에서는 곧바로 틀렸습니다 처리가 되어버린다. 필자도 바로 0.1초컷을 당하고 나서 알게 되었다. 입력받을 때 주의해야겠다.
Author And Source
이 문제에 관하여([백준 14891번] 톱니바퀴 C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@statco19/boj-14891저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)