본문 바로가기
알고리즘 문제풀이/백준

[백준 1780] 종이의 개수

by m2162003 2020. 12. 12.

www.acmicpc.net/problem/1780

 

1780번: 종이의 개수

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

www.acmicpc.net

정답률도 비교적 높고 쉬웠던 문제!

종이가 정사각형 모양으로 계속 잘리므로 길이를 /3해서 진행해준다.

 

#include <stdio.h>
#include <cmath>

using namespace std;

int n;
int arr[3000][3000];

int answer[3];

bool isValid(int len, int row, int col)
{
  int cmp = arr[row][col];

  for (int i = row; i < row + len; i++)
  {
    for (int j = col; j < col + len; j++)
    {
      if (cmp != arr[i][j])
      {
        return false;
      }
    }
  }
  answer[cmp + 1]++;
  return true;
}

void cutPaper(int len, int row, int col)
{
  if (isValid(len, row, col))
  {
    return;
  }

  len = len / 3;
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      cutPaper(len, row + len * i, col + len * j);
    }
  }
}

int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      scanf("%d", &arr[i][j]);
    }
  }

  cutPaper(n, 0, 0);

  for (int i = 0; i < 3; i++)
  {
    printf("%d\n", answer[i]);
  }
  return 0;
}

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1992] 쿼드트리  (0) 2020.12.13
[백준 5904] Moo 게임  (0) 2020.12.12
[백준 16505] 별  (0) 2020.12.12
[백준 2167] 2차원 배열의 합  (0) 2020.12.11
[백준 1941] 소문난 칠공주  (0) 2020.12.11

댓글