[99클럽/코딩테스트 챌린지/C++] 카펫 문제 해결 과정

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

문제 요약

이 문제는 주어진 갈색 격자 수 brown과 노란색 격자 수 yellow를 이용해 카펫의 가로, 세로 크기를 계산하는 문제입니다. 카펫은 테두리가 갈색이고, 가운데 부분이 노란색으로 구성되어 있으며, 다음 조건을 만족해야 합니다:

1. 전체 카펫의 가로와 세로 크기를 구해야 합니다.
2. 카펫의 테두리는 갈색 격자, 가운데는 노란색 격자로 채워져 있습니다.
3. 가로 길이는 세로 길이 이상이어야 합니다.

접근법

1, 카펫의 크기 관계 정의:

• 전체 카펫의 격자 수는 brown + yellow입니다.
• 가로 길이를 X, 세로 길이를 Y라고 할 때, 테두리는 항상 갈색이고, 가운데는 노란색으로 채워져야 하므로:
  • 2x+2(y−2)=brown2(테두리의 갈색 격자 수)
  • (x−2)×(y−2)=yellow(가운데의 노란색 격자 수)

2, 조건을 만족하는 크기 탐색:

• X와 Y는 3 이상이어야 합니다 (테두리가 최소 두 줄이므로).
• X는 Y 이상이어야 합니다.

3, 브루트포스 탐색:

• Y를 3부터 시작하여 y×x=brown+yellowy를 만족하는 모든 경우를 탐색합니다.
• 각 Y에 대해 x=(brown+yellow)/y를 계산하여 확인합니다.

4, 조건 검증:

• 계산된 X와 Y가 2x+2(y−2)=brown와 (x−2)×(y−2)=yellow를 모두 만족하면 결과로 반환합니다.

코드 

// ConsoleApplication2.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int brown = 24;
	int yellow = 24;
	vector<int> answer;
	bool founded = false;
	for (int y = 3; y < brown; y++)
	{
		for (int x = 3; x < brown; x++)
		{
			if (x < y) continue;
			int bc = (x * 2) + ((y - 2) * 2);
			if (bc != brown) continue;
			int yc = (x - 2) * (y - 2);
			if (yc != yellow) continue;
			answer.push_back(x);
			answer.push_back(y);
			founded = true;
			break;
		}
		if (founded) break;
	}

	std::cout << answer[0] << " : " << answer[1] << '\n';

	return 0;
}

배운 점

1, 수학적 관계 정의:

• 문제를 해결하기 위해 조건에 맞는 수학적 관계를 도출하는 것이 중요하다는 점을 배웠습니다.
• 테두리와 내부 격자 수를 활용하여 방정식을 세우고 문제를 간결하게 해결할 수 있었습니다.

2, 효율적인 탐색:

• yyy의 범위를 제한하고, xxx를 계산하여 가능한 경우만 탐색함으로써 브루트포스 탐색의 범위를 줄일 수 있었습니다.

3, 조건 검증:

• 두 가지 조건(테두리의 갈색 격자와 내부의 노란색 격자)이 모두 만족되는지를 꼼꼼히 확인해야 함을 배웠습니다.

결론

이 문제는 수학적 관계를 정확히 정의하고, 효율적으로 탐색하는 방법을 학습할 수 있는 좋은 문제였습니다. 수학적 사고와 조건 검증의 중요성을 다시 한번 느낄 수 있었으며, 이러한 접근 방식은 비슷한 패턴의 문제에서도 활용할 수 있을 것입니다.

 

브루트포스 탐색을 효율적으로 개선하는 방법과, 문제를 해결하기 위해 필요한 수학적 관계를 빠르게 파악하는 능력을 키울 수 있었습니다.