문제
총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.
이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고 톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.
다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.
출력
총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.
1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점
🔎문제분석
8개의 톱니를 가진 톱니바퀴 4개가 존재하고 톱니상태는 N극은 0, S극은 1이다.
회전방향은 시계방향은 1,반시계방향은 -1이다.
톱니바퀴가 회전할때 극에 따라서 옆의 톱니바퀴도 회전할 수 있는데 만약 왼쪽의 톱니바퀴가 회전할때 왼쪽 톱니바퀴의 3시톱니와 오른쪽 톱니바퀴의 9시 톱니가 서로 다른 극을 가지면 오른쪽 톱니바퀴는 왼쪽 톱니바퀴의 반대방향으로 회전을 한다.
💡해결방법
우선 3시, 9시 톱니가 무엇인지 구하기 쉽도록 12시 톱니바퀴가 무엇인지 저장하고 톱니바퀴 회전시 번호를 변경하여 회전을 적용한다.
또한 회전시킬 톱니바퀴를 기준으로 왼쪽에 있는 톱니바퀴들과 오른쪽에 있는 톱니바퀴로 나누어서 양 끝의 톱니바퀴까지 이동하며 회전을 확인하는 방식으로 구현을 한다.
실패코드
#include<iostream>
#include<vector>
using namespace std;
void rotation_left(int g, int dir, vector<vector<int>>& gear, vector<int>& top);
void rotation_right(int g, int dir, vector<vector<int>>& gear, vector<int>& top);
void change_top(int g, int dir, vector<int>& top);
int main() {
vector<vector<int>>gear(4, vector<int>(8,0));//톱니의 상태를 저장할 벡터
vector<int>top(4, 0); //12시 톱니를 저장할 벡터
char c;
for (int i = 0; i < 4; i++) { //톱니상태를 입력받아 저장
for (int j = 0; j < 8; j++) {
cin >> c;//한 글자씩 입력받기 가능!!
gear[i][j] = c - '0';
}
}
int n,r_gear,r_dir; //회전횟수,회전 톱니바퀴, 회전 방향
cin >> n;
for (int i=0; i < n; i++) {
cin >> r_gear >> r_dir;
rotation_left(r_gear - 1, r_dir, gear, top);//왼쪽 톱니바퀴 회전
rotation_right(r_gear - 1, r_dir, gear, top);//오른쪽 톱니바퀴 회전
}
int score = 0;
for (int i = 0, k = 1; i < 4; i++, k *= 2) //점수계산
score = score + k * gear[i][top[i]];
cout << score << endl;
}
void change_top(int g, int dir, vector<int>& top) //톱니바퀴 회전을 구현할 함수
{
top[g] = (top[g] + 8 - dir) % 8; //12시 톱니의 상태를 변경
}
void rotation_left(int g, int dir, vector<vector<int>>& gear, vector<int>& top)
{
if (g == 0) {
change_top(g, dir, top);
return;
}
int left_3 = (top[g - 1] + 2) % 8;
int right_9 = (top[g] + 6) % 8;
if (gear[g - 1][left_3] != gear[g][right_9])
rotation_left(g - 1, -dir, gear, top);
change_top(g, dir, top);
return;
}
void rotation_right(int g, int dir, vector<vector<int>>& gear, vector<int>& top)
{
if (g == 3) {
change_top(g, dir, top);
return;
}
int left_3 = (top[g] + 2) % 8;
int right_9 = (top[g+1] + 6) % 8;
if (gear[g][left_3] != gear[g + 1][right_9])
rotation_right(g + 1, -dir, gear, top);
change_top(g, dir, top);
return;
}
해당코드의 문제점이 rotation_left를 실행하면 회전시킬 톱니바퀴가 회갯 rotation_left에서 회전을 한 상태이기 때문에 결과가 달라지는 문제가 있었다.....
해결하려고 머리를 열심히 굴려봤는데 생각보다 해결법은 간단했다.
시계방향으로 회전을 했으면 반시계방향으로 회전을 시키면 회전하기 전과 동일한 상태가 되는것을 이용하면 간단하게 해결이 가능했다.
수정한 코드
#include<iostream>
#include<vector>
using namespace std;
void rotation_left(int g, int dir, vector<vector<int>>& gear, vector<int>& top);
void rotation_right(int g, int dir, vector<vector<int>>& gear, vector<int>& top);
void change_top(int g, int dir, vector<int>& top);
int main() {
vector<vector<int>>gear(4, vector<int>(8,0));
vector<int>top(4, 0);
char c;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 8; j++) {
cin >> c;
gear[i][j] = c - '0';
}
}
int n,r_gear,r_dir; //회전횟수,회전 톱니바퀴, 회전 방향
cin >> n;
for (int i=0; i < n; i++) {
cin >> r_gear >> r_dir;
rotation_left(r_gear - 1, r_dir, gear, top);
change_top(r_gear-1, -r_dir, top);
rotation_right(r_gear - 1, r_dir, gear, top);
}
int score = 0;
for (int i = 0, k = 1; i < 4; i++, k *= 2)
score = score + k * gear[i][top[i]];
cout << score << endl;
}
void change_top(int g, int dir, vector<int>& top)
{
top[g] = (top[g] + 8 - dir) % 8;
}
void rotation_left(int g, int dir, vector<vector<int>>& gear, vector<int>& top)
{
if (g == 0) {
change_top(g, dir, top);
return;
}
int left_3 = (top[g - 1] + 2) % 8;
int right_9 = (top[g] + 6) % 8;
if (gear[g - 1][left_3] != gear[g][right_9])
rotation_left(g - 1, -dir, gear, top);
change_top(g, dir, top);
return;
}
void rotation_right(int g, int dir, vector<vector<int>>& gear, vector<int>& top)
{
if (g == 3) {
change_top(g, dir, top);
return;
}
int left_3 = (top[g] + 2) % 8;
int right_9 = (top[g+1] + 6) % 8;
if (gear[g][left_3] != gear[g + 1][right_9])
rotation_right(g + 1, -dir, gear, top);
change_top(g, dir, top);
return;
}결과는......
성공했다!!
+
제출을 위해 문제를 검색하다가 톱니바퀴2(골드5) 도찾았다.
톱니바퀴문제와 다른점은 톱니가 4개로 고정이 아닌 N개 라는것과 출력하는 값이 12시 톱니가 S극인 톱니바퀴의 개수를 출력하는것이다르며 다른부분은 동일하다.
입력
첫째 줄에 톱니바퀴의 개수 T (1 ≤ T ≤ 1,000)가 주어진다.
둘째 줄부터 T개의 줄에 톱니바퀴의 상태가 가장 왼쪽 톱니바퀴부터 순서대로 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.
다음 줄에는 회전 횟수 K(1 ≤ K ≤ 1,000)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.
출력
총 K번 회전시킨 이후에 12시방향이 S극인 톱니바퀴의 개수를 출력한다.
해결방법
해결방법은 기본적으로는 톱니바퀴문제의 해결방법과 동일하고 기어의 개수가 고정이 아니기에 몇몇 부분만 코드를 수정하거나 추가해주면 간단하게 해결된다.
1
vector<vector<int>>gear(4, vector<int>(8,0));//톱니의 상태를 저장할 벡터
vector<int>top(4, 0); //12시 톱니를 저장할 벡터
char c;
for (int i = 0; i < 4; i++) { //톱니상태를 입력받아 저장
for (int j = 0; j < 8; j++) {
cin >> c;//한 글자씩 입력받기 가능!!
gear[i][j] = c - '0';
}
}main함수의 해당부분을 아래와 같이 변경
int gear_num;
cin >> gear_num;
vector<vector<int>>gear(gear_num, vector<int>(8, 0));
vector<int>top(gear_num, 0);
char c;
for (int i = 0; i < gear_num; i++) {
for (int j = 0; j < 8; j++) {
cin >> c;
gear[i][j] = c - '0';
}
}2
rotation_right함수의 if (g == 3)을 아래와 같이 변경한다.
if (g == gear.size()-1)수정한 코드
#include<iostream>
#include<vector>
using namespace std;
void rotation_left(int g, int dir, vector<vector<int>>& gear, vector<int>& top);
void rotation_right(int g, int dir, vector<vector<int>>& gear, vector<int>& top);
void change_top(int g, int dir, vector<int>& top);
int main() {
int gear_num;
cin >> gear_num;
vector<vector<int>>gear(gear_num, vector<int>(8, 0));
vector<int>top(gear_num, 0);
char c;
for (int i = 0; i < gear_num; i++) {
for (int j = 0; j < 8; j++) {
cin >> c;
gear[i][j] = c - '0';
}
}
int n,r_gear, r_dir; //회전횟수,회전 톱니바퀴, 회전 방향
cin >> n;
for (int i = 0; i < n; i++) {
cin >> r_gear >> r_dir;
rotation_left(r_gear - 1, r_dir, gear, top);
change_top(r_gear - 1, -r_dir, top);
rotation_right(r_gear - 1, r_dir, gear, top);
}
int score = 0;
for (int i = 0, k = 1; i < gear_num; i++, k *= 2)
score += gear[i][top[i]];
cout << score << endl;
}
void change_top(int g, int dir, vector<int>& top)
{
top[g] = (top[g] + 8 - dir) % 8;
}
void rotation_left(int g, int dir, vector<vector<int>>& gear, vector<int>& top)
{
if (g == 0) {
change_top(g, dir, top);
return;
}
int left_3 = (top[g - 1] + 2) % 8;
int right_9 = (top[g] + 6) % 8;
if (gear[g - 1][left_3] != gear[g][right_9])
rotation_left(g - 1, -dir, gear, top);
change_top(g, dir, top);
return;
}
void rotation_right(int g, int dir, vector<vector<int>>& gear, vector<int>& top)
{
int size=gear.size()-1;
if (g == size) {
change_top(g, dir, top);
return;
}
int left_3 = (top[g] + 2) % 8;
int right_9 = (top[g + 1] + 6) % 8;
if (gear[g][left_3] != gear[g + 1][right_9])
rotation_right(g + 1, -dir, gear, top);
change_top(g, dir, top);
return;
}
+톱니바퀴 풀었다는 가정하에 어려운 문제는 아닌것 같다.
