Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
Tags
- Cloud Pub/Sub
- 다이나믹 프로그래밍
- 삼성 SW 역량테스트
- 삼성SW역량테스트
- 시뮬레이션
- 종만북
- jpa
- Air Table
- LCS
- 접미사 배열
- 우선순위 큐
- ICPC
- r
- Cloud Run
- REACT
- 다익스트라
- 그리디
- 생활코딩
- BFS
- Bit
- 컴퓨터 구조
- 데이터 분석
- CI/CD
- 이분탐색
- 수학
- 고속 푸리에 변환
- JavaScript
- 펜윅 트리
- 백준 1753번
- dp
Archives
- Today
- Total
코딩스토리
백준 14891번 - 톱니바퀴 본문
14891번: 톱니바퀴
총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴
www.acmicpc.net
처음에 너무 복잡하게 생각했었는데 사실 엄청 간단하게 해결할 수 있었다.
문제가 다행히도 매번 톱니바퀴가 회전할 때마다 상태가 변화한 것을 체크해야 하는 것이 아니고 처음 상태에서 회전할 건지 안 할 건지만 판단해주면 되는 문제였다.
아마 이 문제에서의 핵심은 X번 톱니바퀴를 회전시켰을 때 양 옆의 톱니바퀴가 회전할지 안 할지 구하고, 또 양 옆의 톱니바퀴가 회전할지 안 할지 구해야 하는 부분이 가장 구현하기 까다로웠을 것이다.
나는 left와 right란 변수를 두어 범위 안에만 존재한다면 계속 반복할 수 있게 만들었다.
(이게 말로 설명하기 그렇고 아래 코드를 보면 이해하기 쉬움)
다행히도? 톱니바퀴가 4개였기 때문에 시간복잡도는 매우 넉넉했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
typedef pair<bool, int> pbi;
deque<char>dq[4];
pbi turn[4];
void init() {
for (int i = 0; i < 4; i++) {
turn[i] = pbi(false, 0);
}
}
int main() {
int n, k, num, dis;
string str;
for (int i = 0; i < 4; i++) {
cin >> str;
for (int j = 0; j < str.size(); j++) {
char temp = str[j] == '0' ? 'N' : 'S'; // N극과 S극 저장
dq[i].push_back(temp);
}
}
cin >> k;
for (int i = 0; i < k; i++) {
cin >> num >> dis;
init();
turn[num - 1] = pbi(true, dis);
int left = num - 1, right = num - 1;
int t = 3;
while (t--) { // 3번만 돌려도 됨. 어차피 모든 경우는 3번 안에서 판별
left -= 1; right += 1;
if (0 <= left && left < 3) { // 범위 안에 있다면
// 해당 톱니바퀴가 오른쪽 톱니바퀴에 영향을 받음
// 즉 오른쪽 톱니바퀴와 맞닿은 부분을 확인해야 함(서로 상극인지, 이전 톱니바퀴가 회전을 했는지)
if (dq[left][2] != dq[left + 1][6] && turn[left + 1].first == true) turn[left] = pbi(true, turn[left + 1].second * (-1));
}
if (1 <= right && right <= 3) { // 왼쪽과 같이
if (dq[right][6] != dq[right - 1][2] && turn[right - 1].first == true) turn[right] = pbi(true, turn[right - 1].second * (-1));
}
}
for (int j = 0; j < 4; j++) {
if (turn[j].first == true) {
if (turn[j].second == 1) { // 시계방향 회전
dq[j].push_front(dq[j].back());
dq[j].pop_back();
}
else { // 반시계방향 회전
dq[j].push_back(dq[j].front());
dq[j].pop_front();
}
}
}
}
int ans = 0, mul = 1;
for (int i = 0; i < 4; i++) {
if (dq[i][0] == 'S') ans += mul;
mul *= 2;
}
cout << ans << "\n";
}
|
cs |
뭔가 구현 문제는 설명하기가 귀찮다..
어쨌든 나쁘지 않은 퀄리티의 문제였다!
'알고리즘 > 삼성 SW 역량테스트 기출 문제' 카테고리의 다른 글
백준 17822번 - 원판 돌리기 (0) | 2021.03.19 |
---|---|
백준 15685번 - 드래곤 커브 (0) | 2021.03.17 |
백준 17144번 - 미세먼지 안녕! (0) | 2020.08.17 |
백준 16235번 - 나무 재테크 (0) | 2020.08.15 |
백준 16236번 - 아기상어 (0) | 2020.08.13 |
Comments