백준 2163번 초콜릿자르기 C++ 구현해보기

---

```

백준 2163번 초콜릿자르기 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 2163번 풀이

---

https://www.acmicpc.net/problem/2163

2163번: 초콜릿 자르기

 

 

백준 2163번 초콜릿자르기는

난이도 쉬움 등급의 문제로서

 

N x M 사이즈의 초콜릿 케이크를

가로 N 세로 M 개의 1 x 1 블럭으로 이뤄진 초콜릿 케이크로 나누는데 

필요한 최소한의 자르기를 구하는 문제입니다.

 

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

예를들어

8 x 6 사이즈의 케이크를

40개의 조각으로 나눈다면

 

칼질을 최소화 하기 위해

최대한 긴 부분을 자르기 위해

 

(8-1)번 초록색 자르기를 시전하고

(6-1)*8번 빨간색 자르기를 시전하면 

 

1  x 1 자르기가 됩니다.

 

이를 NM으로 바꾸면

 

(N-1) + (M-1)*N 입니다.

 

여기서 최소값은 

N이 M보다 커야 더 작을 것 입니다.

 

이를 코딩으로 구현하면

 

전체 코드는 다음과 같습니다

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>

class CMinCut {
	
private:
	std::string inputStr;

public:

	CMinCut()
	{

	}

	~CMinCut()
	{

	}

	/* 입력 */
	void getUserInput()
	{
		std::string tempStr;
		std::getline(std::cin, tempStr);
		inputStr = tempStr;
	}

	/* 합 출력 */
	void printMinCut()
	{
		const int answer = findMinCut();
		std::cout << answer << "\n";
	}

	int findMinCut()
	{
		int retVal = 0;
		std::stringstream ss(inputStr);

		int num1;
		int num2;

		ss >> num1;
		ss >> num2;

		if (num1 < num2)
		{
			std::swap(num1, num2);
		}

		return retVal = (num1 - 1) + (num2 -1) * num1;
	}

};



int main()
{

	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	CMinCut* cMinCut = new CMinCut();
	cMinCut->getUserInput();
	cMinCut->printMinCut();
	delete cMinCut;
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---