[백준] 종이의 개수

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

1780번: 종이의 개수

 

1. 문제 조건 정리(변형)

a) R(-1), G(0), B(1)이 있는 큰 종이가 있습니다.

b) 단색이면 자르지 않고 해당 색 개수를 늘립니다.

c) 단색이 아니면 9등분을 하여 위 과정을 다시 반복합니다.

 

2. 입력 데이터

- N = 3^7 = 약 2000개 입니다

 

3. 아이디어

- 영역을 줄여나가며 구현만 하면 됩니다.

- 반복과정이 있으니 재귀함수를 사용하면 됩니다.

 

- 매번 N^2으로 단색인지를 확인하여야 합니다.

- 9등분한 영역을 재귀 호출하므로(확인 요망)

- O(N^2 * logN) 입니다.

 

5. 구현

a) 종료 조건

- 모두 단색인 경우 자르지 않으므로 단색일 때 함수를 종료합니다.

- 어쩔 수 없이 모든 값을 순회하여야 같은 색임을 알 수 있습니다.*

 

b) 재귀 함수 호출 

- 9등분한 영역에 대한 재귀함수를 호출합니다.

 

c) 파라미터

- 현재 종이의 크기와 절대 좌표 값을 알아야 합니다.

- 저는 좌상단을 기준으로 한 row, col 값과 size값을 파라미터로 설정하였습니다.

 

6. 문법

- 2차원 배열 선언 : paper = [[int(x) for x in input().split()]for y in range(n)]

 

7. 코드

def isSameKind(sr, sc, sz):
  global paper  
  color = paper[sr][sc]
  for r in range(sr, sr + sz):
    for c in range(sc, sc + sz):
      if paper[r][c] != color:
        return False
  return True

def cutPaper(sr, sc, sz):
  if isSameKind(sr, sc, sz):
    global paper, paperCnt
    paperCnt[paper[sr][sc]] += 1
    return
  
  newSz = sz//3
  for i in range(3):
    for j in range(3):
      cutPaper(sr + i*newSz, sc + j*newSz, newSz)

  
  
n = int(input())
paper = [[int(x) for x in input().split()]for y in range(n)]
paperCnt = [0, 0, 0]

cutPaper(0, 0, n)

print(paperCnt[-1])
print(paperCnt[0])
print(paperCnt[1])

 

8. 추가 사항

- * 누적합을 통한 성능향상이 가능할지 모르겠습니다..