일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- backtracking
- priority_queue
- 종만북
- stack
- 문자열
- 유니온파인드
- 분리집합
- 백준
- acm
- 세그먼트트리
- union-find
- 완전탐색
- 재귀
- 너비우선탐색
- BFS
- 다이나믹프로그래밍
- BOJ
- 이분탐색
- 그리디
- 분할정복
- 알고리즘문제해결전략
- 누적합
- 스택
- DFS
- Algospot
- 백트래킹
- DP
- Greedy
- 동적계획법
- 알고스팟
- Today
- Total
DAMPER's blog
[ALGOSPOT] CLOCKSYNC 본문
출처 : algospot.com/judge/problem/read/CLOCKSYNC
algospot.com :: CLOCKSYNC
Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 ��
algospot.com
문제
그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.
시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.
0 |
0, 1, 2 |
1 |
3, 7, 9, 11 |
2 |
4, 10, 14, 15 |
3 |
0, 4, 5, 6, 7 |
4 |
6, 7, 8, 10, 12 |
5 |
0, 2, 14, 15 |
6 |
3, 14, 15 |
7 |
4, 5, 7, 14, 15 |
8 |
1, 2, 3, 4, 5 |
9 |
3, 4, 5, 9, 13 |
시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 개수 C (<= 30) 가 주어진다.
각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.
출력
각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1 을 출력한다.
<아이디어>
1. 스위치를 4번이상 돌릴 필요가 없다. 4번째 돌리면 제자리로 돌아오기 때문에 안 돌린 것과 마찬가지.
2. 모든 스위치를 0~3번 돌리는 것으로 완전탐색.
<구현>
테이블을 5개씩으로 맞추기 위해 5개 미만인 열은 -1로 채워주고, 시계를 돌릴 때 -1이 나오면 멈춰준다.
최소값을 987654321로 하고 모두 12시를 가리키고 있을 때 최소값을 갱신해준다.
pos는 스위치 번호로 0부터 9까지 재귀적으로 스위치를 0~3번 돌린다.
0~3번 돌릴 때마다 다음 스위치를 돌릴지 정하는 함수를 진입한다.
<실수한 부분>
1. 모든 시계가 12시를 가리키고 있는 지 체크하는 함수에서 16개의 시계를 확인해야하는데 15개만 확인했다.
2. 모든 경우에서 불가능한 경우를 처리하지 않았다.
이런 실수는 무조건 줄여야하며, 실전에서는 범하지 말아야 합니다.
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
66
67
68
69
70
71
|
#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
int rotatea[10][5] = {
{0, 1, 2, -1, -1},
{3, 7, 9, 11, -1},
{4, 10, 14, 15, -1},
{0, 4, 5, 6, 7},
{6, 7, 8, 10, 12},
{0, 2, 14, 15, -1},
{3, 14, 15, -1, -1},
{4, 5, 7, 14, 15},
{1, 2, 3, 4, 5},
{3, 4, 5, 9, 13},
};
lld mncnt = 987654321LL;
bool check(vector<int>& v)
{
for(int i=0;i<16;i++)
if(v[i]!=12)
return false;
return true;
}
void rotates(vector<int>& v, int k)
{
for(int i=0;i<5;i++)
{
if(rotatea[k][i]==-1) break;
v[rotatea[k][i]] = (v[rotatea[k][i]]+3)%12 ? (v[rotatea[k][i]]+3)%12:12;
}
}
void f(int pos, vector<int>& v, lld cnt)
{
if(pos==10)
{
if(check(v)) mncnt = min(cnt, mncnt);
return;
}
for(int i=0;i<4;i++)
{
f(pos+1, v, cnt+i);
rotates(v, pos);
}
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int tc;
cin>>tc;
while(tc--)
{
vector<int> v(16);
mncnt = 987654321LL;
for(int i=0;i<16;i++)
cin>>v[i];
f(0, v, 0LL);
if(mncnt==987654321LL) cout<<-1<<endl;
else cout<<mncnt<<endl;
}
return 0;
}
|
cs |
다음 코드는 책을 참고하여 backtracking 느낌으로 바꾼 코드입니다.
이런 코드 스타일을 연습하지 않아서인지 많이 서툰 것 같습니다.
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
66
67
|
#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
int rotatea[10][5] = {
{0, 1, 2, -1, -1},
{3, 7, 9, 11, -1},
{4, 10, 14, 15, -1},
{0, 4, 5, 6, 7},
{6, 7, 8, 10, 12},
{0, 2, 14, 15, -1},
{3, 14, 15, -1, -1},
{4, 5, 7, 14, 15},
{1, 2, 3, 4, 5},
{3, 4, 5, 9, 13},
};
bool check(vector<int>& v)
{
for(int i=0;i<16;i++)
if(v[i]!=12)
return false;
return true;
}
void rotates(vector<int>& v, int k)
{
for(int i=0;i<5;i++)
{
if(rotatea[k][i]==-1) break;
v[rotatea[k][i]] = (v[rotatea[k][i]]+3)%12 ? (v[rotatea[k][i]]+3)%12:12;
}
}
lld f(int pos, vector<int>& v)
{
if(pos==10) return check(v)? 0:987654321LL;
lld ret = 987654321LL;
for(int i=0;i<4;i++)
{
ret = min(i+f(pos+1, v), ret);
rotates(v, pos);
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int tc;
cin>>tc;
while(tc--)
{
vector<int> v(16);
for(int i=0;i<16;i++)
cin>>v[i];
lld res = f(0, v);
if(res==987654321LL) cout<<-1<<endl;
else cout<<res<<endl;
}
return 0;
}
|
cs |
'Problem Solving > 알고리즘 문제해결전략' 카테고리의 다른 글
[알고리즘 문제해결전략] 메모이제이션 (0) | 2020.10.15 |
---|---|
[ALGOSPOT] JUMPGAME (0) | 2020.10.09 |
[ALGOSPOT] QUADTREE (0) | 2020.10.02 |
[ALGOSPOT] BOARDCOVER (0) | 2020.09.25 |
[ALGOSPOT] PICNIC (0) | 2020.09.24 |