에브리타임 창의력 문제

오늘 새벽 1시 반. 우리 학교 에브리타임 자유 게시판에 누가 제발 이것 좀 풀어달라며 위의 사진을 올렸다.

나도 풀어보다가 경우의 수가 너무 많을 것 같아서 이걸 어떻게 풀지...하다가 갑자기 코딩으로 풀 수 있지 않을까? 하는 생각에 무작정 도전해봤다.

우선 계산은 고사하고, 가능한 모든 조합을 만들어 보려 했다. dfs로 육각형의 모든 지점을 차례차례 방문하며 수식을 만들어 모든 점을 방문하면 출력을 하게 했다. 예상대로 무수히 많은 조합이 만들어졌고 아래가 그 예시이다. 몇 천개는 생기지 않았을까 생각이 들었다. 그러던 중 작성자가 답을 찾았다고 했고 열심히 코딩하던 나는 김이 새서 그만 풀려고 했는데, 코딩으로 가능한지 궁금하다는 댓글이 달렸고 다시 힘을 내서 풀게 되었다.

문자열의 수식 계산을 어떻게 할 지 계속 고생하다가 결국 풀어냈고, 풀고나니 별 건 없었지만 너무 뿌듯했다.

드디어 풀어낸 정답!

---

우선 육각형 입력값을 2차원 배열로 표현했다.

그 후 dfs로 모든 지점에서 가능한 모든 조합을 생성한다. 조합이 완성되면 해당하는 문자열이 정답인지를 판단한다.

정답은 isPossible 함수로 판별하는데 이 함수는 문자열 str을 등호를 기준으로 좌, 우 문자열로 나눈다. 그 후 좌, 우 문자열을 계산해서 두 값이 같다면 정답이고 true를 반환하는 함수이다.

문자열을 숫자로 계산하는 함수 toNum에서 고생을했다. 문자열을 일일이 검사하면서 숫자와 연산자를 각각 스택에 쌓아서 계산했다. 뺄셈이 최대 두번, 나눗셈이 최대 한 번임을 감안해서 간단하게 계산했다.

주석을 보면 대부분 이해가 될 것 같다.

 

다 풀고나니 별 게 없는 것 같다. 그래도 이 새벽에 포기하지 않고 끝까지 풀고 결과를 만들어내서 뿌듯하다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%97%90%ED%83%80.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
using namespace std;

int p[10][10] = {
	{-1,-1,-1,-1,-1,-1},
	{-1,11,5,3,-1,-1}, 
	{-1,3,1,12,7,-1},
	{-1,13,9,3,2,-1},
	{-1,-1,9,7,13,-1},
	{-1,-1,-1,-1,-1,-1}
};
int visit[10][10];

int dx[6] = { -1,0,0,1,-1,1 }; // 각각 육각형에서 좌상, 우상, 좌하, 우하, 좌, 우로 이동하는 좌표
int dy[6] = { -1,-1,1,1,0,0 };

//문자열을 계산해서 결과값 반환
int toNum(string str) {
	int num = 0; //문자열에서 연산자로 나뉘는 각 숫자. ex) 123 - 45에서 123과 45가 이에 해당
	stack<int> st; //숫자를 저장하는 스택
	stack<int> op; //연산자를 저장하는 스택. 편의상 뺄셈은 1, 나눗셈은 0으로 저장했다.

	for (int i = 0; i < str.size(); i++) {
		//숫자인 경우 num 최신화
		if (str[i] - '0' >= 0 && str[i] - '0' < 10) { 
			num *= 10;
			num += (str[i] - '0');
		}

		//연산자인 경우 num을 st스택에 넣고 연산자도 op 스택에 넣는다.
		else if (str[i] == '-') { 
			st.push(num);
			num = 0;
			op.push(1);
		}
		else if (str[i] == '/') {
			st.push(num);
			num = 0;
			op.push(2);
		}
	}
	//마지막에 삽입 안 된 숫자도 넣어준다.
	if(num !=0) st.push(num); 

	//st에 마지막 결과값 한 개만 남을 때까지 연산한다.
	while (st.size() > 1) {
		//st의 상위 숫자 두 개와 연산자를 뽑아낸다.
		int b = st.top(); st.pop();
		int a = st.top(); st.pop();
		int oper = op.top(); op.pop();

		//나눗셈인 경우 나눠서 다시 스택에 넣어준다.
		if (oper == 2) {
			st.push(a / b);
			if (a%b != 0) return -1; // 나눗셈 연산이 안 되는 경우는 불가능하므로 -1 반환해서 끝낸다.
		}
		else {
			//스택이 비어있다는 것은 딱 a - b 계산만 남았다는 뜻이므로 계산하고 넣어준다.
			if (st.empty() || op.empty()) { 
				st.push(a - b);
			}

			// aa / a - b 같은 경우다. a-b를 먼저 계산하면 사칙연산 순서에 맞지 않으므로 aa/a를 계산하고 b와 계산한다.
			// 이때 st가 empty라는 것은 aa / a - b라는 것이고, empty()가 아니라면 x - aa / a - b가 될 수 있으므로 b를 더해줘야한다.
			else if (op.top() == 2) { 
				op.pop();
				int aa = st.top(); st.pop();
				if (aa%a != 0) return -1;
				if (st.empty())
					st.push(aa / a - b);
				else
					st.push(aa / a + b);
			}
			else if (op.top() == 1) {
				st.push(a + b);
			}
		}
	}
	return st.top();
}

bool isPossible(string str) {
	//등호를 기준으로 문자열을 1, 2로 나눈다. 
	string str1 = "", str2 = "";
	int pos = str.find('=');
	str1 = str.substr(0, pos);
	str2 = str.substr(pos+1);

	//예외처리 : 각 문자열의 시작이나 끝에 연산자가 있으면 false
	if (str1[0] == '-' || str1[0] == '/' ||
		str1[str1.size() - 1] == '-' || str1[str1.size() - 1] == '/' ||
		str2[0] == '-' || str2[0] == '/' ||
		str2[str2.size() - 1] == '-' || str2[str2.size() - 1] == '/')
		return false;

	//등호를 기준으로 나눈 문자열을 계산해서 숫자로 반환했을 때 같다면 true 반환
	if (toNum(str1) == toNum(str2))
		return true;

	return false;
}

void dfs(int x, int y, string str) {
	
	if (str.size() == 14) {
		if (str[0] == '=' || str[str.size() - 1] == '=') return; // 예외 처리 : 문자열 시작이나 끝에 등호 있을시 return
		if(isPossible(str)) //str이 정답을 만들어내면 출력하고 끝내기
			cout << str << endl;
		return;
	}
	
	for (int i = 0; i < 6; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (visit[nx][ny] == 1) continue;
		if (p[nx][ny] == -1) continue;
		visit[nx][ny] = 1;
		if (p[nx][ny] == 11) str += '=';
		else if (p[nx][ny] == 12) str += '/';
		else if (p[nx][ny] == 13) str += '-';
		else str += to_string(p[nx][ny]);
		dfs(nx, ny, str);
		visit[nx][ny] = 0;
		str.erase(str.size()-1);
	}
}

int main()
{
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			if (p[i][j] == -1) continue;
			if (p[i][j] > 10) continue;
			memset(visit, 0, sizeof(visit));
			visit[i][j] = 1; 
			string tmp = to_string(p[i][j]);
			dfs(i, j, tmp); // 숫자인 지점을 시작점으로 dfs 조사
		}
	}
}