KoreanFoodie's Study
[종만북 문제] Synchronizing Clocks, 시계 맞추기 (문제 ID : CLOCKSYNC, 난이도 : 중) 본문
Data Structures, Algorithm/종만북
[종만북 문제] Synchronizing Clocks, 시계 맞추기 (문제 ID : CLOCKSYNC, 난이도 : 중)
GoldGiver 2024. 3. 4. 22:40
프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!
핵심 :
1. 완전 탐색 문제이긴 하지만, 문제를 살짝 변형해서 생각하면 좋다.
[종만북 문제] Synchronizing Clocks, 시계 맞추기 (문제 ID : CLOCKSYNC, 난이도 : 중)
이 문제는 .. 여전히 완전탐색으로 풀 수 있다.
다만, 사실 잘 보면 스위치를 누르는 순서는 상관이 없다는 것을 눈치챌 수 있다. 따라서, 스위치 10개를 최대 3번씩 눌러가면서 답을 찾아나가면 된다. 최대 상한은 4^10 이 될 것이다! 😉
#include <iostream>
#include "stdlib.h"
#include <vector>
using namespace std;
#define MINVAL(x, y) (((x) > (y)) ? y : x)
#define MAXVAL(x, y) (((x) > (y)) ? x : y)
int ans;
int clocks[16];
// 사실 30번 이상 스위치를 눌러야 하면, 답이 없는 경우이다.
const int INF = 99999;
// 마지막 스위치에 도달했을 경우
const int LAST = 10;
// 스위치가 이동시키는 시계
vector<vector<int>> switches =
{
{0, 1, 2},
{3, 7, 9, 11},
{4, 10, 14, 15},
{0, 4, 5, 6, 7},
{6, 7, 8, 10, 12},
{0, 2, 14, 15},
{3, 14, 15},
{4, 5, 7, 14, 15},
{1, 2, 3, 4, 5},
{3, 4, 5, 9, 13}
};
void pressSwitch(int sw)
{
for (int cl : switches[sw])
clocks[cl] = (clocks[cl] + 1) % 4;
}
// 모든 시계가 12 시인지 체크
bool allPass()
{
for (int cl : clocks)
if (cl != 3)
return false;
return true;
}
int sol(int curSw)
{
// 끝까지 와서 체크한 결과 문제 없으면 답 갱신 시도
if (curSw == LAST)
{
if (allPass())
return 0;
return INF;
}
// 4 번 돌리면 원위치이므로, 3번까지만 돌리면 된다
int ans = INF;
for (int i = 0; i < 4; ++i)
{
ans = MINVAL(ans, i + sol(curSw + 1));
pressSwitch(curSw);
}
return ans;
}
void outputHandler()
{
int ans = sol(0);
if (ans >= INF)
ans = -1;
cout << ans << endl;
}
void inputHandler()
{
for (int i = 0; i < 16; ++i)
{
cin >> clocks[i];
clocks[i] = (clocks[i] / 3) - 1;
}
}
int main()
{
int cases;
cin >> cases;
while (cases--)
{
inputHandler();
outputHandler();
}
return 0;
}
'Data Structures, Algorithm > 종만북' 카테고리의 다른 글
[종만북 문제] 울타리 잘라내기 (문제 ID : FENCE, 난이도 : 중) (1) | 2024.03.05 |
---|---|
[종만북 문제] 쿼드 트리 뒤집기 (문제 ID : QUADTREE, 난이도 : 하) (0) | 2024.03.05 |
[종만북 문제] 게임판 덮기 (문제 ID : BOARDCOVER, 난이도 : 하) (0) | 2024.03.04 |
[종만북 문제] 소풍 (문제 ID : PICNIC, 난이도 : 하) (0) | 2024.03.03 |
[종만북 문제] 보글 게임 (문제 ID : BOGGLE, 난이도 : 하) (0) | 2024.03.03 |
Comments