1 문제
알고리즘 문제 해결 전략의 세 번째 문제, 생각보다 쉽게 풀었다! 한 3트만에 성공한 듯. 재귀에 대한 이해느는 것 같아 기쁘다 ㅎㅎ
2 문제 해결 알고리즘
- 독해: 문제를 읽고 이해한다.
- 재정의+추상화: 문제를 익숙한 용어로 재정의한다.
- 설계: 어떻게 해결할지 계획을 세운다.
- 검증: 계획을 검증한다.
- 구현: 프로그램을 구현한다.
- 회고: 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
2-1 독해
16개의 시계가 주어지고, 각 시계는 3, 6, 9, 12의 값을 가진다. 여기서 10개의 스위치가 주어지는데, 각 스위치는 몇 개의 시계와 연결되어 있다. 스위치를 누르면 연결된 몇 개의 시계가 3시간 씩 돌아간다. 스위치를 최소한으로 눌러 모든 시계를 12시로 맞출 때, 최소의 버튼 누름 횟수를 구하라는 문제이다.
각 시계는
3,6,9,12의 값을 가짐: 3을 더하는 함수, 3을 빼는 함수를 각각 구현해야겠다는 생각이 드는 대목이다. 특히 3에서 3을 빼면 12, 12에서 3을 더하면 3이 됨을 예외 케이스로 처리해야 할 것이다.
각 스위치는 몇 개의 시계와 연결됨: 무슨 자료구조로 해당 데이터를 저장하면 좋을까? 나는 벡터 배열을 떠올렸다. 우선 스위치가 10개로 고정되어 있으니 배열을 쓰고, 각 스위치가 연결되어 있는 시계는 순회되어 활용될 것이 자명하기 때문에 벡터로 표현하면 좋을 것 같다. 백터 배열은 보드판 덮기 문제 (BOARDCOVER)에서 배웠다.
최소의 버튼 누름 횟수를 구하라: 최적화 문제이다. 최적화 문제는 다음과 같은 방식으로 풀 수 있다.
1. 완전 탐색
2. 동적 계획법
3. 조합 탐색
4. 최적화 문제를 결정 문제로 바꾸기
이번 문제에서는 재귀를 이용한 완전 탐색을 통해 해결한다.
2-2 재정의+추상화
조금만 더 생각해보면, 어차피 한 스위치는 4번 이상 누르지 못한다. (정확히는, 한 스위치를 4번 이상 누르면 그것과 동일한 결과를 내는 최소 누름 횟수가 존재한다.) 왜냐하면 시계가 낼 수 있는 모양이 4종류 밖에 없고, 4번 누르면 제자리로 돌아오기 때문이다. 즉, 시계가 낼 수 있는 모양은 주기가 4인 주기 함수로 볼 수 있다.
따라서, 각 스위치 누름의 횟수는 '0, 1, 2, 3' 4개 중 하나이다. 즉 이 문제는 10개의 스위치 각각의 누름의 횟수를 '0, 1, 2, 3'로 대입시켜보며 모든 시계를 12시로 만드는 최소 버튼 누름 개수를 확인하면 된다.
2-3 설계
2-3-a 직관
수많은 재귀를 이용한 완전 탐색 문제를 풀어보았던 시점에서... 재귀를 이용하면 될 것이라는 생각은 든다. 하지만 어떻게 코드를 작성해야 할지는 아직 잘 모르겠다 ㅠㅠ
2-3-b 체계적인 접근
2-3-b-1 비슷한 문제를 풀어본 적이 있나?
비슷한 문제를 풀어본 적이 있다. 바로 예제로 주어진 여행하는 외판원 문제이다. (책 165p) 이 문제는 도시와 도시들 간 거리가 주어질 때, 모든 도시들을 방문하는 경로들 중 가장 짧은 것의 길이를 구하는 문제이다.
예제 코드는 다음과 같다.
int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시 간의 거리를 저장하는 배열
// path: 지금까지 만든 경로
// visited: 각 도시의 방문 여부
// currentLength: 지금까지 만든 경로의 길이
// 나머지 도시들을 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
// 기저 사례: 모둔 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
if(path.size() == n)
return currentLength + dist[path[0]][path.back()];
double ret = INF; // 매우 큰 값으로 초기화
// 다음 방문할 도시들을 전부 시도해 본다.
for(int next = 0; next < n; ++next) {
if(visited[next]) continue;
int here = path.back();
path.push_back(next);
visited[next] = true;
// 나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
double cand = shortestPath(path, visited, currentLength + dist[here][next];
ret = min(ret, cand);
visited[next] = false;
path.pop_back();
}
return ret;
}요런 느낌?
- 다음 선택할 스위치를 모두 시도해보며 (for문)
- 각 과정 안에서 남은 스위치의 선택을 재귀 호출을 통해 완성하고 횟수를 구한다.
이렇게 풀면 되지 않을까?
2-3-b-2 단순한 방법에서 시작할 수 있나?
사실, 여기까지 생각이 들었다면... 그냥 연립 방정식으로 풀 수도 있지 않을까? 굳이 재귀를 하지 말고, 다중 for문을 구현하여 모든 경우를 탐색하는 것이다. 코드를 작성한다면 아마 이런 느낌일 것이다.
int minCntForClockSync() {
int ret = 987654321;
for (int x0 = 0; x0 < 4; ++x0) {
for (int x1 = 0; x1 < 4; ++x1) {
for (int x2 = 0; x2 < 4; ++x2) {
for (int x3 = 0; x3 < 4; ++x3) {
for (int x4 = 0; x4 < 4; ++x4) {
for (int x5 = 0; x5 < 4; ++x5) {
for (int x6 = 0; x6 < 4; ++x6) {
for (int x7 = 0; x7 < 4; ++x7) {
for (int x8 = 0; x8 < 4; ++x8) {
for (int x9 = 0; x9 < 4; ++x9) {
resOfCalc(x0, x1, x2, x3, x4, x5, x6, x7, x8, x9);
if (clocksAllNoon()) {
ret = min(ret, x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9);
}
}
}
}
}
}
}
}
}
}
}
return ret;
}
물론 코드가 더욱 더러워지기는 했지만... 시간복잡도의 측면에서도 크게 차이가 없어 보인다.
2-4 검증
10개의 스위치가 있는데, 각 스위치가 (0, 1, 2, 3)의 값을 가질 수 있으므로 관찰하는 경우의 수는 4^10 = 2^20이므로 1억이 안된다. 물론 각 경우에 대한 구현이 어떻게 되느냐에 따라 시간은 더 들 수 있겠지만, 쉽게 10초를 넘기지는 못할 것이다. 즉, 완전 탐색으로 풀어도 문제가 되지는 않을 것이다.
2-5 구현
2-5-1 재귀로 완전 탐색하는 방법
첫 번째 시도 (FAILED)
#include <bits/stdc++.h>
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;
// variable
vector<int> clocks(16);
vector<int> switchConnectTo[10] = {
{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}
};
int switchPushed[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
void printClocks() {
for (int i = 0; i < 16; ++i) {
cout << clocks[i] << " ";
}
cout << endl;
}
void plusThreeInClocks(int idx) {
if (clocks[idx] == 12) clocks[idx] = 3;
else clocks[idx] += 3;
}
void minusThreeInClocks(int idx) {
if (clocks[idx] == 3) clocks[idx] = 12;
else clocks[idx] -= 3;
}
bool clocksAllNoon() {
for (int i = 0; i < 16; ++i) {
if (clocks[i] != 12) return false;
}
return true;
}
bool allSwitchPushedFewerThanFour() {
for (int i = 0; i < 10; ++i) {
if (switchPushed[i] >= 4) return false;
}
return true;
}
int minCntForClockSync(int cnt) {
// printClocks();
if (clocksAllNoon()) return cnt;
if (!allSwitchPushedFewerThanFour()) return 987654321;
int ret = 987654321;
for (int s = 0; s < 10; ++s) {
switchPushed[s]++;
for (int c : switchConnectTo[s]) {
plusThreeInClocks(c);
}
int cand = minCntForClockSync(cnt + 1);
ret = min(ret, cand);
switchPushed[s]--;
for (int c : switchConnectTo[s]) {
minusThreeInClocks(c);
}
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int c;
cin >> c;
while(c--) {
for (int i = 0; i < 16; i++) {
cin >> clocks[i];
}
int ans = minCntForClockSync(0);
if (ans == 987654321) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}- 만약 모두 12시로 맞춰지면
cnt를 반환한다. - 만약 하나의 스위치라도 4번 이상 눌렸으면 이건 일단 답(최소 누름 횟수)이 아니므로
INF값을 반환한다. ret값을INF로 정의하고, 모든 스위치들에 대하여 스위치 누르고 -> 재귀하여 결과 값 받고 -> 스위치 안눌렀다 치고 를 반복하여 결과 값의 최솟값을 얻는다.ret을 반환한다.
결과는...
시간 초과! ㅠㅠ
첫 번째 시도 패인
allSwitchPushedFewerThanFour() 이 함수에서 시간을 많이 잡아먹는 것으로 추론했다. (사실 문제는 이게 아니었지만... 후술 예정) 어차피 switchPushed 배열로 스위치의 누름 횟수를 알 수 있으니 누름 횟수가 4 이상이라면 호출을 하지 않아 굳이 확인 함수를 만들지 않고도 호출 횟수를 줄일 수 있을 것이다! 수정한 코드는 다음과 같다.
두 번째 시도 (FAILED)
`
#include <bits/stdc++.h>
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;
// variable
vector<int> clocks(16);
vector<int> switchConnectTo[10] = {
{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}
};
int switchPushed[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
void printClocks() {
for (int i = 0; i < 16; ++i) {
cout << clocks[i] << " ";
}
cout << endl;
}
void plusThreeInClocks(int idx) {
if (clocks[idx] == 12) clocks[idx] = 3;
else clocks[idx] += 3;
}
void minusThreeInClocks(int idx) {
if (clocks[idx] == 3) clocks[idx] = 12;
else clocks[idx] -= 3;
}
bool clocksAllNoon() {
for (int i = 0; i < 16; ++i) {
if (clocks[i] != 12) return false;
}
return true;
}
int minCntForClockSync(int cnt) {
// printClocks();
if (clocksAllNoon()) return cnt;
int ret = 987654321;
for (int s = 0; s < 10; ++s) {
if (switchPushed[s] >= 3) continue;
switchPushed[s]++;
for (int c : switchConnectTo[s]) {
plusThreeInClocks(c);
}
int cand = minCntForClockSync(cnt + 1);
ret = min(ret, cand);
switchPushed[s]--;
for (int c : switchConnectTo[s]) {
minusThreeInClocks(c);
}
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int c;
cin >> c;
while(c--) {
for (int i = 0; i < 16; i++) {
cin >> clocks[i];
}
int ans = minCntForClockSync(0);
if (ans == 987654321) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}추가한 코드는 다음과 같다.
if (switchPushed[s] >= 3) continue;for문 안에 다음 코드를 작성함으로써 만약 현재 스위치 누름 횟수가 3 이상이라면 누를 필요가 없으므로 (0, 1, 2, 3이 가능한 경우인데 가능한 경우를 모두 돎) continue를 통해 for문을 건너 뛸 수 있다.
결과는?
또! 시간초과... 뭐가 문제인지 곰곰히 생각해보니...! 아!
두 번째 시도 패인
switchPushed를 출력해보니...
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0 0
3 2 0 0 0 0 0 0 0 0
3 3 0 0 0 0 0 0 0 0
3 3 1 0 0 0 0 0 0 0
3 3 2 0 0 0 0 0 0 0
3 3 3 0 0 0 0 0 0 0
3 3 3 1 0 0 0 0 0 0
3 3 3 2 0 0 0 0 0 0
3 3 3 3 0 0 0 0 0 0
3 3 3 3 1 0 0 0 0 0
3 3 3 3 2 0 0 0 0 0
3 3 3 3 3 0 0 0 0 0
3 3 3 3 3 1 0 0 0 0
3 3 3 3 3 2 0 0 0 0
3 3 3 3 3 3 0 0 0 0
3 3 3 3 3 3 1 0 0 0
3 3 3 3 3 3 2 0 0 0
3 3 3 3 3 3 3 0 0 0
3 3 3 3 3 3 3 1 0 0
3 3 3 3 3 3 3 2 0 0
3 3 3 3 3 3 3 3 0 0
3 3 3 3 3 3 3 3 1 0
3 3 3 3 3 3 3 3 2 0
3 3 3 3 3 3 3 3 3 0
3 3 3 3 3 3 3 3 3 1
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 1
3 3 3 3 3 3 3 3 3 1
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 1 1
3 3 3 3 3 3 3 3 2 1
3 3 3 3 3 3 3 3 3 1
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 1 2
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 1 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 0 1
3 3 3 3 3 3 3 3 1 1
3 3 3 3 3 3 3 3 2 1
3 3 3 3 3 3 3 3 3 1
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 1 2
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 1 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 0 2
3 3 3 3 3 3 3 3 1 2
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 1 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 0 3
3 3 3 3 3 3 3 3 1 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 2 1 0
3 3 3 3 3 3 3 3 1 0
3 3 3 3 3 3 3 3 2 0
3 3 3 3 3 3 3 3 3 0
3 3 3 3 3 3 3 3 3 1
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 1
3 3 3 3 3 3 3 3 3 1
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 1 1
3 3 3 3 3 3 3 3 2 1
3 3 3 3 3 3 3 3 3 1
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
...처음에는 경우의 수를 잘 세다가 뒤로 갈수록 이상해진다. 순회의 첫 부분을 알려줄 부분이 필요해보인다!
세 번째 시도 (SUCCESS)
#include <bits/stdc++.h>
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;
// variable
vector<int> clocks(16);
vector<int> switchConnectTo[10] = {
{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}
};
int switchPushed[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
void printClocks() {
for (int i = 0; i < 16; ++i) {
cout << clocks[i] << " ";
}
cout << endl;
}
void plusThreeInClocks(int idx) {
if (clocks[idx] == 12) clocks[idx] = 3;
else clocks[idx] += 3;
}
void minusThreeInClocks(int idx) {
if (clocks[idx] == 3) clocks[idx] = 12;
else clocks[idx] -= 3;
}
bool clocksAllNoon() {
for (int i = 0; i < 16; ++i) {
if (clocks[i] != 12) return false;
}
return true;
}
int minCntForClockSync(int cnt, int startIdx) {
// printClocks();
if (clocksAllNoon()) return cnt;
int ret = 987654321;
for (int s = startIdx; s < 10; ++s) {
if (switchPushed[s] >= 3) continue;
switchPushed[s]++;
for (int c : switchConnectTo[s]) {
plusThreeInClocks(c);
}
int cand = minCntForClockSync(cnt + 1, s);
ret = min(ret, cand);
switchPushed[s]--;
for (int c : switchConnectTo[s]) {
minusThreeInClocks(c);
}
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int c;
cin >> c;
while(c--) {
for (int i = 0; i < 16; i++) {
cin >> clocks[i];
}
int ans = minCntForClockSync(0, 0);
if (ans == 987654321) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}startIdx를 추가하였다.
스위치 눌림 배열을 출력해보면?
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0 0
3 2 0 0 0 0 0 0 0 0
3 3 0 0 0 0 0 0 0 0
3 3 1 0 0 0 0 0 0 0
3 3 2 0 0 0 0 0 0 0
3 3 3 0 0 0 0 0 0 0
3 3 3 1 0 0 0 0 0 0
3 3 3 2 0 0 0 0 0 0
3 3 3 3 0 0 0 0 0 0
3 3 3 3 1 0 0 0 0 0
3 3 3 3 2 0 0 0 0 0
3 3 3 3 3 0 0 0 0 0
3 3 3 3 3 1 0 0 0 0
3 3 3 3 3 2 0 0 0 0
3 3 3 3 3 3 0 0 0 0
3 3 3 3 3 3 1 0 0 0
3 3 3 3 3 3 2 0 0 0
3 3 3 3 3 3 3 0 0 0
3 3 3 3 3 3 3 1 0 0
3 3 3 3 3 3 3 2 0 0
3 3 3 3 3 3 3 3 0 0
3 3 3 3 3 3 3 3 1 0
3 3 3 3 3 3 3 3 2 0
3 3 3 3 3 3 3 3 3 0
3 3 3 3 3 3 3 3 3 1
3 3 3 3 3 3 3 3 3 2
3 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 2 1
3 3 3 3 3 3 3 3 2 2
3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 1 1
3 3 3 3 3 3 3 3 1 2
3 3 3 3 3 3 3 3 1 3
3 3 3 3 3 3 3 3 0 1
3 3 3 3 3 3 3 3 0 2
3 3 3 3 3 3 3 3 0 3
3 3 3 3 3 3 3 2 1 0
3 3 3 3 3 3 3 2 2 0
3 3 3 3 3 3 3 2 3 0
3 3 3 3 3 3 3 2 3 1
3 3 3 3 3 3 3 2 3 2
3 3 3 3 3 3 3 2 3 3
3 3 3 3 3 3 3 2 2 1
3 3 3 3 3 3 3 2 2 2
3 3 3 3 3 3 3 2 2 3
3 3 3 3 3 3 3 2 1 1
3 3 3 3 3 3 3 2 1 2
3 3 3 3 3 3 3 2 1 3
3 3 3 3 3 3 3 2 0 1
3 3 3 3 3 3 3 2 0 2
3 3 3 3 3 3 3 2 0 3
3 3 3 3 3 3 3 1 1 0
3 3 3 3 3 3 3 1 2 0
3 3 3 3 3 3 3 1 3 0
3 3 3 3 3 3 3 1 3 1
3 3 3 3 3 3 3 1 3 2
3 3 3 3 3 3 3 1 3 3
3 3 3 3 3 3 3 1 2 1
3 3 3 3 3 3 3 1 2 2
3 3 3 3 3 3 3 1 2 3
3 3 3 3 3 3 3 1 1 1
3 3 3 3 3 3 3 1 1 2
3 3 3 3 3 3 3 1 1 3
3 3 3 3 3 3 3 1 0 1
3 3 3 3 3 3 3 1 0 2
3 3 3 3 3 3 3 1 0 3
3 3 3 3 3 3 3 0 1 0
3 3 3 3 3 3 3 0 2 0
3 3 3 3 3 3 3 0 3 0
3 3 3 3 3 3 3 0 3 1
3 3 3 3 3 3 3 0 3 2
3 3 3 3 3 3 3 0 3 3
3 3 3 3 3 3 3 0 2 1
3 3 3 3 3 3 3 0 2 2
3 3 3 3 3 3 3 0 2 3
3 3 3 3 3 3 3 0 1 1
3 3 3 3 3 3 3 0 1 2
3 3 3 3 3 3 3 0 1 3
3 3 3 3 3 3 3 0 0 1
3 3 3 3 3 3 3 0 0 2
3 3 3 3 3 3 3 0 0 3
3 3 3 3 3 3 2 1 0 0
3 3 3 3 3 3 2 2 0 0
3 3 3 3 3 3 2 3 0 0
3 3 3 3 3 3 2 3 1 0
3 3 3 3 3 3 2 3 2 0
3 3 3 3 3 3 2 3 3 0
3 3 3 3 3 3 2 3 3 1
3 3 3 3 3 3 2 3 3 2
3 3 3 3 3 3 2 3 3 3
3 3 3 3 3 3 2 3 2 1
3 3 3 3 3 3 2 3 2 2
3 3 3 3 3 3 2 3 2 3
3 3 3 3 3 3 2 3 1 1
3 3 3 3 3 3 2 3 1 2
3 3 3 3 3 3 2 3 1 3
3 3 3 3 3 3 2 3 0 1
3 3 3 3 3 3 2 3 0 2
3 3 3 3 3 3 2 3 0 3
3 3 3 3 3 3 2 2 1 0
3 3 3 3 3 3 2 2 2 0
3 3 3 3 3 3 2 2 3 0
3 3 3 3 3 3 2 2 3 1
3 3 3 3 3 3 2 2 3 2
3 3 3 3 3 3 2 2 3 3
3 3 3 3 3 3 2 2 2 1
3 3 3 3 3 3 2 2 2 2
3 3 3 3 3 3 2 2 2 3
3 3 3 3 3 3 2 2 1 1
3 3 3 3 3 3 2 2 1 2
3 3 3 3 3 3 2 2 1 3
3 3 3 3 3 3 2 2 0 1
3 3 3 3 3 3 2 2 0 2
3 3 3 3 3 3 2 2 0 3
3 3 3 3 3 3 2 1 1 0
3 3 3 3 3 3 2 1 2 0
3 3 3 3 3 3 2 1 3 0
3 3 3 3 3 3 2 1 3 1
3 3 3 3 3 3 2 1 3 2
3 3 3 3 3 3 2 1 3 3
3 3 3 3 3 3 2 1 2 1
3 3 3 3 3 3 2 1 2 2
3 3 3 3 3 3 2 1 2 3
3 3 3 3 3 3 2 1 1 1
3 3 3 3 3 3 2 1 1 2
3 3 3 3 3 3 2 1 1 3
3 3 3 3 3 3 2 1 0 1
3 3 3 3 3 3 2 1 0 2
3 3 3 3 3 3 2 1 0 3
3 3 3 3 3 3 2 0 1 0
3 3 3 3 3 3 2 0 2 0
3 3 3 3 3 3 2 0 3 0
3 3 3 3 3 3 2 0 3 1
3 3 3 3 3 3 2 0 3 2
3 3 3 3 3 3 2 0 3 3
3 3 3 3 3 3 2 0 2 1
3 3 3 3 3 3 2 0 2 2
3 3 3 3 3 3 2 0 2 3
3 3 3 3 3 3 2 0 1 1
3 3 3 3 3 3 2 0 1 2
3 3 3 3 3 3 2 0 1 3
3 3 3 3 3 3 2 0 0 1
3 3 3 3 3 3 2 0 0 2
3 3 3 3 3 3 2 0 0 3
3 3 3 3 3 3 1 1 0 0
3 3 3 3 3 3 1 2 0 0
3 3 3 3 3 3 1 3 0 0
3 3 3 3 3 3 1 3 1 0
3 3 3 3 3 3 1 3 2 0
3 3 3 3 3 3 1 3 3 0
3 3 3 3 3 3 1 3 3 1
3 3 3 3 3 3 1 3 3 2
3 3 3 3 3 3 1 3 3 3
3 3 3 3 3 3 1 3 2 1
3 3 3 3 3 3 1 3 2 2
3 3 3 3 3 3 1 3 2 3
3 3 3 3 3 3 1 3 1 1
3 3 3 3 3 3 1 3 1 2
3 3 3 3 3 3 1 3 1 3
3 3 3 3 3 3 1 3 0 1
3 3 3 3 3 3 1 3 0 2
3 3 3 3 3 3 1 3 0 3
3 3 3 3 3 3 1 2 1 0
3 3 3 3 3 3 1 2 2 0
3 3 3 3 3 3 1 2 3 0
3 3 3 3 3 3 1 2 3 1
3 3 3 3 3 3 1 2 3 2
3 3 3 3 3 3 1 2 3 3
3 3 3 3 3 3 1 2 2 1
3 3 3 3 3 3 1 2 2 2
3 3 3 3 3 3 1 2 2 3
3 3 3 3 3 3 1 2 1 1
3 3 3 3 3 3 1 2 1 2
3 3 3 3 3 3 1 2 1 3
3 3 3 3 3 3 1 2 0 1
3 3 3 3 3 3 1 2 0 2
3 3 3 3 3 3 1 2 0 3
3 3 3 3 3 3 1 1 1 0
3 3 3 3 3 3 1 1 2 0
3 3 3 3 3 3 1 1 3 0
3 3 3 3 3 3 1 1 3 1
3 3 3 3 3 3 1 1 3 2
3 3 3 3 3 3 1 1 3 3
3 3 3 3 3 3 1 1 2 1
3 3 3 3 3 3 1 1 2 2
3 3 3 3 3 3 1 1 2 3
3 3 3 3 3 3 1 1 1 1
3 3 3 3 3 3 1 1 1 2
3 3 3 3 3 3 1 1 1 3
3 3 3 3 3 3 1 1 0 1
3 3 3 3 3 3 1 1 0 2
3 3 3 3 3 3 1 1 0 3
3 3 3 3 3 3 1 0 1 0
3 3 3 3 3 3 1 0 2 0
3 3 3 3 3 3 1 0 3 0
3 3 3 3 3 3 1 0 3 1
3 3 3 3 3 3 1 0 3 2
3 3 3 3 3 3 1 0 3 3
3 3 3 3 3 3 1 0 2 1
3 3 3 3 3 3 1 0 2 2
3 3 3 3 3 3 1 0 2 3
3 3 3 3 3 3 1 0 1 1
3 3 3 3 3 3 1 0 1 2
3 3 3 3 3 3 1 0 1 3
3 3 3 3 3 3 1 0 0 1
3 3 3 3 3 3 1 0 0 2
3 3 3 3 3 3 1 0 0 3
3 3 3 3 3 3 0 1 0 0
3 3 3 3 3 3 0 2 0 0
3 3 3 3 3 3 0 3 0 0
3 3 3 3 3 3 0 3 1 0
3 3 3 3 3 3 0 3 2 0
3 3 3 3 3 3 0 3 3 0
3 3 3 3 3 3 0 3 3 1
3 3 3 3 3 3 0 3 3 2
3 3 3 3 3 3 0 3 3 3
3 3 3 3 3 3 0 3 2 1
3 3 3 3 3 3 0 3 2 2
3 3 3 3 3 3 0 3 2 3
3 3 3 3 3 3 0 3 1 1
3 3 3 3 3 3 0 3 1 2
3 3 3 3 3 3 0 3 1 3
3 3 3 3 3 3 0 3 0 1
3 3 3 3 3 3 0 3 0 2
3 3 3 3 3 3 0 3 0 3
3 3 3 3 3 3 0 2 1 0
3 3 3 3 3 3 0 2 2 0
3 3 3 3 3 3 0 2 3 0
3 3 3 3 3 3 0 2 3 1
3 3 3 3 3 3 0 2 3 2
3 3 3 3 3 3 0 2 3 3
3 3 3 3 3 3 0 2 2 1
3 3 3 3 3 3 0 2 2 2
3 3 3 3 3 3 0 2 2 3
3 3 3 3 3 3 0 2 1 1
3 3 3 3 3 3 0 2 1 2
3 3 3 3 3 3 0 2 1 3
3 3 3 3 3 3 0 2 0 1
3 3 3 3 3 3 0 2 0 2
3 3 3 3 3 3 0 2 0 3
3 3 3 3 3 3 0 1 1 0
3 3 3 3 3 3 0 1 2 0
3 3 3 3 3 3 0 1 3 0
3 3 3 3 3 3 0 1 3 1
3 3 3 3 3 3 0 1 3 2
3 3 3 3 3 3 0 1 3 3
3 3 3 3 3 3 0 1 2 1
3 3 3 3 3 3 0 1 2 2
3 3 3 3 3 3 0 1 2 3
3 3 3 3 3 3 0 1 1 1
3 3 3 3 3 3 0 1 1 2
3 3 3 3 3 3 0 1 1 3
3 3 3 3 3 3 0 1 0 1
3 3 3 3 3 3 0 1 0 2
3 3 3 3 3 3 0 1 0 3
3 3 3 3 3 3 0 0 1 0
3 3 3 3 3 3 0 0 2 0
3 3 3 3 3 3 0 0 3 0
3 3 3 3 3 3 0 0 3 1
3 3 3 3 3 3 0 0 3 2
3 3 3 3 3 3 0 0 3 3
3 3 3 3 3 3 0 0 2 1
3 3 3 3 3 3 0 0 2 2
3 3 3 3 3 3 0 0 2 3
3 3 3 3 3 3 0 0 1 1
3 3 3 3 3 3 0 0 1 2
3 3 3 3 3 3 0 0 1 3
3 3 3 3 3 3 0 0 0 1
3 3 3 3 3 3 0 0 0 2
3 3 3 3 3 3 0 0 0 3
...배열이 경우의 수를 잘 세고 있음을 알 수 있다.
결과는?
성공!
좋은 코드를 작성하기 위한 원칙 적용
- 간결한 코드 작성: 답을 내기 위한 변수
clocks,switchConnectedTo,switchPushed를 글로벌 변수로 작성했다. - 적극적으로 코드 재사용: 3시간을 더하는 함수
plusThreeInClocks(), 3시간을 빼는 함수minusThreeInClocks(), 모든 시계가 12시를 가리키고 있는지 확인하는 함수clocksAllNoon(), 으로 함수를 쪼개어 적극적으로 재사용했다. 덕분에 정답 코드가 훨씬 간결하고, 이해하기 쉬워졌다. - 표준 라이브러리 공부:
vector<int>를 적극적으로 사용했다. 특히switchConnectedTo의 경우vector<int>를 원소로 가지는 배열로써, 후에 범위 기반 반복문 문법을 사용하여 코드의 간결성을 높일 수 있었다. (for (int c : switchConnectTo[s])) - 항상 같은 형태로 프로그램 작성: TSL 알고리즘 정답 코드와 유사한 형태로 작성되었다.
- 명료한 명명법 사용:
clocks,switchConnectedTo,switchPushed,plusThreeInClocks(),minusThreeInClocks(),clocksAllNoon()등 모두 명료한 이름을 가진다. - 자료 정규화하여 저장: 딱히 정규화가 사용될 부분은 없었다. 굳이 생각해보자면 문제를 푸는 과정에서 각 스위치가 눌린 횟수 만이 결과에 영향을 준다는 점? (즉, 순서가 중요하지 않다는 점... 근데 이건 자료 정규화가 아니다)
- 코드와 데이터 분리하기:
switchConnectTo[10]가 대표적인 예이다. 각 스위치가 어느 시계와 연결되어 있는지에 대한 데이터인데, 코드와 분리됨으로서 코드의 양을 줄인다.
2-5-2 중첩 반복문으로 완전 탐색하는 방법
그냥 10중 for문을 만들어서 코드를 작성해도 원리 상으로는 별 차이가 없지 않을까?
코드를 작성하기 전에는 만만해보였는데 막상 코드를 작성하려니 애먹었다;; 많이 작성해보지 않은 코드여서 그런듯
#include <bits/stdc++.h>
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;
// variable
vector<int> clocks(16);
vector<int> switchConnectTo[10] = {
{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 plusThreeInClocks(vector<int>& _clocks, int idx) {
if (_clocks[idx] == 12) _clocks[idx] = 3;
else _clocks[idx] += 3;
}
bool clocksAllNoon(vector<int> _clocks) {
for (int i = 0; i < 16; ++i) {
if (_clocks[i] != 12) return false;
}
return true;
}
vector<int> resOfCalc(int v0, int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8, int v9) {
vector<int> resClocks = clocks;
while(v0--) {
for (int c : switchConnectTo[0]) {
plusThreeInClocks(resClocks, c);
}
}
while(v1--) {
for (int c : switchConnectTo[1]) {
plusThreeInClocks(resClocks, c);
}
}
while(v2--) {
for (int c : switchConnectTo[2]) {
plusThreeInClocks(resClocks, c);
}
}
while(v3--) {
for (int c : switchConnectTo[3]) {
plusThreeInClocks(resClocks, c);
}
}
while(v4--) {
for (int c : switchConnectTo[4]) {
plusThreeInClocks(resClocks, c);
}
}
while(v5--) {
for (int c : switchConnectTo[5]) {
plusThreeInClocks(resClocks, c);
}
}
while(v6--) {
for (int c : switchConnectTo[6]) {
plusThreeInClocks(resClocks, c);
}
}
while(v7--) {
for (int c : switchConnectTo[7]) {
plusThreeInClocks(resClocks, c);
}
}
while(v8--) {
for (int c : switchConnectTo[8]) {
plusThreeInClocks(resClocks, c);
}
}
while(v9--) {
for (int c : switchConnectTo[9]) {
plusThreeInClocks(resClocks, c);
}
}
return resClocks;
}
int minCntForClockSync() {
int ret = 987654321;
for (int x0 = 0; x0 < 4; ++x0) {
for (int x1 = 0; x1 < 4; ++x1) {
for (int x2 = 0; x2 < 4; ++x2) {
for (int x3 = 0; x3 < 4; ++x3) {
for (int x4 = 0; x4 < 4; ++x4) {
for (int x5 = 0; x5 < 4; ++x5) {
for (int x6 = 0; x6 < 4; ++x6) {
for (int x7 = 0; x7 < 4; ++x7) {
for (int x8 = 0; x8 < 4; ++x8) {
for (int x9 = 0; x9 < 4; ++x9) {
vector<int> newClocks(16);
newClocks = resOfCalc(x0, x1, x2, x3, x4, x5, x6, x7, x8, x9);
if (clocksAllNoon(newClocks)) {
ret = min(ret, x0 + x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9);
}
}
}
}
}
}
}
}
}
}
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int c;
cin >> c;
while(c--) {
for (int i = 0; i < 16; i++) {
cin >> clocks[i];
}
int ans = minCntForClockSync();
if (ans == 987654321) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}- 10중 for문으로 가능한 모든 순열을 찾는다.
- 입력으로 받은
clocks에서 10개의 스위치를 주어진 순열만큼 만큼 누른 결과를 저장한다. - 만약 결과 속 시계들이 모두 12시를 가리키고 있으면,
ret는 스위치 누른 총 횟수의 최솟값으로 바꾼다.
결과는?
정답! 하지만 시간은 약 5초 정도 걸렸고, 이는 재귀를 사용했을 때보다 10배 정도 느린 수치이다.
2-6 회고
2-6-1 최적화 문제 with 반복 완전 탐색 Tip
반복 완전 탐색을 이용한 최적화 문제(최대 최소 문제)의 알짜 코드는 다음과 같다.
int minCnt(){
// 고를 수 있는 원소들의 집합 순회하며 최솟값 찾기
int ret = INF;
for(next = 원소 in 고를 수 있는 원소들의 집합) {
int cand = next를 처리한 결과;
ret = min(ret, cand);
}
return ret;
}- for문 밖에서
ret를INF로 정의 - 선택 가능한 모든 원소에 대하여
- 반환 후보
cand정의 후next를 처리하여cand답 채우기 ret = min(ret, cand);
최적화 문제 with 반복 완전 탐색 문제는 다음과 같은 과정을 거친다.
1. for문 밖에서ret를INF로 정의
2. 선택 가능한 모든 원소에 대하여
3. 반환 후보cand정의 후next를 이용하여cand답 채우기
4.ret = min(ret, cand);
2-6-2 최적화 문제 with 재귀 완전 탐색 Tip
재귀 완전 탐색을 이용한 최적화 문제(최대 최소 문제)의 알짜 코드는 다음과 같다.
int minCnt(vector<int>& path, int cnt){
if (주어진 조건 충족) {
return cnt;
}
if (주어진 조건 미충족) {
return INF;
}
// 고를 수 있는 원소들의 집합 순회하며 재귀함수 호출
int ret = INF;
for(next = 원소 in 고를 수 있는 원소들의 집합) {
path.push_back(next);
int cand = minCnt(path, cnt+1);
ret = min(ret, cand);
path.pop_back();
}
return ret;
}- for문 밖에서
ret를INF로 정의 - 해당 단계에서 선택 가능한 모든 원소에 대하여 원소 고르기
- 반환 후보
cand정의 후 재귀,ret = min(ret, cand) - 원소 빼기
최적화 문제 with 재귀 완전 탐색 문제는 다음과 같은 과정을 거친다.
1. for문 밖에서ret를INF로 정의
2. 해당 단계에서 선택 가능한 모든 원소에 대하여 원소 고르기
3. 반환 후보cand정의 후 재귀,ret = min(ret, cand)
4. 원소 뺀 후 다음 원소 선택 ... (2번으로 돌아감)
2-6-3 INF는 무슨 값을 써야 좋을까?
책 68p를 보면 987654321을 사용하라고 나와 있다. 이유는 2^30에 가까운 매우 큰 값이면서 서로 더해지더라도 32bit signed int에서 오버플로우를 내지 않고, 1000000000보다 오타가 났는지 눈으로 확인하기도 용이하기 때문이다.
const int INF = 987654321
INF값은987654321을 사용하자!
여담으로, 위에 코드를 작성할 때 한 가지 놓쳤던 것이, INF 변수를 사용하지 않고 987654321을 그대로 정답 코드에 작성했다는 점이다. 이는 컴파일러가 잡아주지 못하는 상수 오타를 발생시킬 수 있으므로, 안 좋은 코드이다. (반성!)
2-6-4 reference는 언제 써야할까?
반복문을 이용한 풀이에서 보면 함수들에게 reference로 벡터를 인자로 전달하는 경우가 있다.
void plusThreeInClocks(vector<int>& _clocks, int idx) {
if (_clocks[idx] == 12) _clocks[idx] = 3;
else _clocks[idx] += 3;
}reference는 어떤 local 변수를 함수 내부에서 수정하고 싶을 때 사용한다. 이때, type 뒤에 &를 붙여주면 된다.
reference는 어떤 local 변수를 함수 내부에서 수정하고 싶을 때 사용한다. 이때, type 뒤에&를 붙여주면 된다.
여담으로, reference와 pointer에 대한 설명은 다음 링크를 참고한다.
2-6-5 답이 없는 경우에 -1 출력하기
문제에서 요구하는 대로 답이 없는 경우에 -1을 출력하고자, minCntForClockSync()에서 직접 -1을 출력하려고 하면 어렵다. 왜냐하면 해당 함수는 답이 없는 경우에 INF를 반환하기 때문이다. 따라서 함수 내에서 직접-1을 반환하려고 하지 말고, 마지막에 답을 출력할 때 답이 INF라면 -1을 대신 출력해주면 된다.
답이 없는 경우에
-1을 출력하라고 하면, 함수 내에서 직접-1을 반환하려고 하지 말고, 마지막에 답을 출력할 때 답이 매우 크다면-1을 대신 출력해주면 된다.
3 구종만's Sol
3-1 구종만's 재정의
처음 깨달아야 하는 것은, 예제 입출력 설명이 유도하는 방향과는 다르게 스위치를 누르는 순서는 결과에 전혀 중요하지 않다는 점이다. 두 스위치를 누르는 순서를 바꾼다고 해서 그 결과는 바뀌지 않는다. 따라서 우리가 계산해야 할 것은 각 스위치를 몇 번이나 누를 것이냐 뿐이다.
두번째로 깨달아야 하는 것은, 어떤 스위치건 간에 누를 수 있는 최대 횟수는 3번이라는 것이다. 왜냐하면 어떤 스위치를 네 번 누르면 연결된 시계들은 모두 12시간씩 앞으로 이동하니 하나도 누르지 않은 것과 다름이 없기 때문이다. 따라서 각 스위치를 누르는 횟수는 0에서 3 사이의 정수이다.
3-2 구종만's 검증
10개의 스위치가 있으니 전체 경우의 수는 4^10 = 2^20, 일반적으로 시간 안에 모든 경우를 세어 볼 수 있다. 따라서 완전 탐색으로 무난하게 풀 수 있을 것이다.
3-3 구종만's 구현
const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
const char linked[SWITCHES][CLOCKS + 1] = {
"xxx.............",
"...x...x.x.x....",
"....x.....x...xx",
"x...xxxx........",
"......xxx.x.x...",
"x.x...........xx",
"...x..........xx",
"....xx.x......xx",
".xxxxx..........",
"...xxx...x...x.."
};
// 모든 시계가 12시를 가리키는지 확인
bool areAligned(const vector<int>& clocks) {
for (int i = 0; i < 16;i++) {
if (clocks[i] != 12) {
return false;
}
}
return true;
}
// swtch번 스위치를 누름
void push(vector<int>& clocks, int swtch) {
for (int clock = 0; clock < CLOCKS; ++clock) {
if (linked[swtch][clock] == 'x') {
clocks[clock] += 3;
if (clocks[clock] == 15)
clocks[clock] = 3;
}
}
}
// swtch: 이번에 누를 스위치의 번호 및 남은 스위치들의 시작 번호
// 가 주어질 때, 남은 스위치들을 눌러서 clocks를 12로 맞출 수 있는 최소 횟수를 반환한다.
// 만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch) {
if (swtch == SWITCHES) {
return areAligned(clocks) ? 0 : INF;
}
int ret = INF;
for (int cnt = 0; cnt < 4; ++cnt) {
ret = min(ret, cnt + solve(clocks, swtch + 1));
push(clocks, swtch);
}
return ret;
}3-4 구종만's 구현을 읽고 또 회고
3-4-1 선택 가능한 원소의 기준이 무엇인가
나는 선택 가능한 원소의 기준을 다음에 누를 스위치로 보았고, 종만 씨는 선택 가능한 원소의 기준을 스위치를 누를 횟수로 보았다.
결과적으로, 스위치를 누를 횟수로 재귀하는 것이 맞았다. 왜냐하면 앞서 언급했듯, 스위치를 누르는 순서는 중요하지 않기 때문이다. 내가 세운 기준은 다음에 누를 스위치로 순서 정보가 포함되어 있다. 따라서 순서를 고려하지 않기 위해 startIdx가 필요했던 것이다.
문제 풀이를 설계하는 과정이 얼마나 중요한지.. 알게 되었다. 또 선택 가능한 원소들의 기준을 고를 때 신중을 기해야겠다는 생각이 들었다.
선택 가능한 원소: 뽑는 순서인가 뽑힌 횟수인가?
3-4-2 데이터 저장 방식
솔직히 linked[SWITCHES][CLOCKS + 1]보다는 switchConnectTo[10]가 더 낫지 않나 싶다.
linked[SWITCHES][CLOCKS + 1]
const char linked[SWITCHES][CLOCKS + 1] = {
"xxx.............",
"...x...x.x.x....",
"....x.....x...xx",
"x...xxxx........",
"......xxx.x.x...",
"x.x...........xx",
"...x..........xx",
"....xx.x......xx",
".xxxxx..........",
"...xxx...x...x.."
};switchConnectTo[10]
vector<int> switchConnectTo[10] = {
{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}
};후자가 더 나은 이유는, 내부 원소를 순회할 때 전자는 x인지 아닌지를 판별해야하는 반면, 후자는 그냥 반복문으로 간단하게 처리할 수 있기 때문이다. 더욱이 vector<int>이기 때문에, 범위 기반 반복문을 사용하면 코드 간결성은 배가 될 것이다.
linked[SWITCHES][CLOCKS + 1]
void push(vector<int>& clocks, int swtch) {
for (int clock = 0; clock < CLOCKS; ++clock) {
if (linked[swtch][clock] == 'x') {
clocks[clock] += 3;
if (clocks[clock] == 15)
clocks[clock] = 3;
}
}
}switchConnectTo[10] by 도열
void plusThreeInClocks(int idx) {
if (clocks[idx] == 12) clocks[idx] = 3;
else clocks[idx] += 3;
}
...
for (int c : switchConnectTo[s]) {
plusThreeInClocks(c);
}
...내가 적은 코드가 훨씬 간결 한 것 같다.
벡터 배열을 적극적으로 활용하여 코드의 간결성을 높히자!
4 끝
종만: "한 번 푼 문제를 다시 본다고 해서 배우는 것이 있을까 생각할 수도 있지만, 오히려 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 더 많습니다."
또 볼게요... 근데 이제 ps에서 살짝 무게를 줄여야 할 것 같은 느낌이다. 개인 프로젝트를 미뤄놓고 ps만 붙잡고 있다 ㅠㅠ
안녕하세요. 오도열입니다.