[백준/C++] 삼각 초콜릿 포장 (Sweet)

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 규칙을 찾으면 쉽게 풀 수 있는 문제다.

 

빨간색 포장은 아래에 육각형이 두개 붙은 삼각형, 파란색 포장은 위에 육각형이 두개 붙은 삼각형 모양이다.

 

삼각형 포장의 각 줄 마다 맨 왼쪽의 index를 0이라고 가정하자.

이때, 빨간색 삼각형 모양의 포장의 윗부분 육각형의 index를 i라고하면 아래에 있는 육각형의 index는 i, i+1이 된다.

 

즉, 각 줄을 y라고 하면 빨간색 삼각형으로 포장지를 채우기 위해서는 'R' == [y][i] == [y+1][i] == [y+1][i+1]이 성립해야 한다는 것이다.

 

파란색도 비슷하게 조건을 찾을 수 있다.

 

파란색의 맨 왼쪽 위 육각형의 좌표를 [y][i]라고 하면, 파란색 삼각형으로 포장을 완성하기 위해서는

'B' == [y][i] == [y][i+1] == [y+1][i+1] 이 성립해야 한다.

 

그리고 2중 for문으로 육각형을 탐색하는데, 이때 항상 맨 윗줄에서 아래줄로 탐색하고 왼쪽에서 오른쪽으로 탐색하기 때문에 빨간색 삼각형은 항상 맨위에 있는 삼각형을 처음 발견하고, 파란 삼각형은 항상 맨 왼쪽 위에 있는 삼각형을 발견하게 된다.

 

그러므로 위 조건을 만족하는지 검사하고, 검사한 좌표에 있는 육각형들이 이전에 다른 삼각형을 만드는데 사용이 되었는지 체크해 답을 출력했다.

 

​

[아이디어 정리]

1. 2중 for문으로 탐색을 시작하고 이전에 삼각형을 만드는데 사용되지 않은 육각형을 만나면 탐색을 시작한다.
2. 육각형의 색깔에 따라 조건에 맞춰 탐색하고 만약 조건에 부합하지 않으면 0을 출력한다.
3. 전부 탐색이 완료 됐을 경우 1을 출력한다.

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;


void Calc(vector<vector<bool>> &visited, vector<string> &strV, int N)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (!visited[i][j])
			{
				if (strV[i][j] == 'R')
				{
					if (i + 1 >= N)
					{
						cout << 0;
						return;
					}
					if (strV[i + 1][j] == 'R' && strV[i + 1][j + 1] == 'R'&&!visited[i + 1][j]&&!visited[i + 1][j + 1])
					{
						visited[i + 1][j] = true;
						visited[i + 1][j + 1] = true;
					}
					else 
					{
						cout << 0; return;
					}
				}
				else 
				{
					if (j + 1 > i) 
					{
						cout << 0;
						return;
					}
					if(strV[i][j+1] == 'B' && strV[i + 1][j + 1] == 'B'&&!visited[i][j + 1]&&!visited[i + 1][j + 1])
					{
						visited[i][j+1] = true;
						visited[i+1][j + 1] = true;
					}
					else 
					{
						cout << 0;
						return;
					}
				}
			}
		}
	}
	cout << 1;
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N=0;
	cin >> N;
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	vector<string> strV(N);
	for (int n = 0; n < N; n++)
	{
		cin >> strV[n];
	}
	Calc(visited, strV, N);	
	return 0;
}

 

---

 

조건만 찾으면 쉬운 문제라 쉽게 풀 수 있었다.

 

31462번: 삼각 초콜릿 포장 (Sweet)