[백준 / BOJ] 14754 Pizza Boxes

문제

출처 : www.acmicpc.net/problem/14754

14754번: Pizza Boxes

해설

n과 m이 주어지고, 각 칸에 해당하는 값이 주어진다. 

이때, n * m 육면체를 정면, 옆면에서 봤을때, 모양은 각 줄에서 가장 큰 값에 해당한다. 이때, 모양을 바꾸지않으면서 가장 많은 블록을 제거하는 값을 찾으면된다.

 

풀이

Y축을 기준으로 n*m배열을 완전탐색해준다. 

for(i =1; i <= n)

for(j = 1; j <= m) 이런식으로..

 

1. i 축에 해당하는 모든 블록에서 최댓값을 찾아준다. (이는 해당하는 줄을 대표하는 가장큰 블록이다.)

2. 이때, check[해당블록의 i][해당블록의 j]값에 해당하는 값을 한번도 안 더해줬다면, 전역변수에 더해준후, check[해당하는 i][해당하는 j]를 1로 만든다.

3. 위를 i = 1; i <= n까지 반복한다.

위 과정을 반복하면, 측면에서 봤을때 각 줄의 최댓값들을 알수있다.

이 과정을 가로축또한 마찬가지로 해준다. 그러면 정면에서 봤을때의 최댓값이 나오고, arr을 전부다 더해준값에서 빼주면 답이나온다.

 

한 idx 최댓값이 10^9이라 전부 더해줄경우 int범위를 초과한다. long long int를 사용해야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14754%20Pizza%20Boxes/main.cpp

devxb/JJUNalgo