[ BOJ / 파이썬 ] 1780 종이의 개수

(22.08.25)

 

/ 다시 제출 /

import sys
input = sys.stdin.readline


n = int(input())

paper = [list(map(int, input().split())) for _ in range(n)]

typeCount = {-1:0, 0:0, 1:0}

def cut(x, y, n):
  if n == 1:
    typeCount[paper[x][y]] += 1
    return
  type = checkPaper(x, y, n)

  if type != None:
    typeCount[type] += 1
    return
  else:
    for i in range(3):
      for j in range(3):
        cut(x + (i * (n // 3)), y + (j * (n//3)), n //3)

def checkPaper(x, y, n):
  for i in range(n):
    for j in range(n):
      if paper[x][y] != paper[x+i][y+j]:
        return None
  return paper[x][y]

cut(0, 0, n)
for value in typeCount.values():
  print(value)

 

사람 사고방식이 어디 가지는 않는건지 이전 코드구현과 거의 유사하게 풀었다.

네이밍은 이전 버전이 나은 것 같아서 가져와서 변경한 코드이다.

 

---

 

이 문제에서 체크해야할 것.

 

1. 종이를 쪼개는 부분 구현( 범위 주의 )

2. 종이를 체크할 때의 로직에서 범위 설정

3. 재귀 중단 시점 설정 + 중단 시점에 할 일

 

: 1.부분

    : 우선 가로 세로 3구역으로 자르니 -> 2중 for문으로 range(3)으로 하면 되겠군. ( 총 9개의 구역 나온다.)

    : 각 구역은 시작X, 시작Y가 정의되어 cut함수에 들어가야 한다. -> 현재 시작 값에 일정 범위씩 더해주면 되겠군.

        -> 현재 전체 길이/3이 늘리는 기준 값이 될 것이고, 점차 늘어야하는데 이건 2중 for문의 i가 곱해지면 되겠군.

 

: 2.부분

    : 시작 값과  &  시작값에서 현재 시점 종이길이까지 차근 차근 x,y늘린 값을 비교한다.

 

: 3.부분

: 재귀 문제치곤 재귀 중단 시점 설정 결정과 행동 정의는 꽤 쉽다.

    : 종이의 길이가 1이거나, 종이 내의 모든 숫자가 같을 때.

    : 중단 시점에 그 종이의 첫 번째 값의 카운트를 올려준다. 

 

 

 

아예 처음 시작 기준 값 0, 0과 아예 처음 시작 길이값 n으로 자르는 함수 호출한다. 그리고 연산을 마친 뒤에는 

 

그리고 딕셔너리의 값만 가져오는 values()에서 value를 차례차례 출력한다.

 

 

 

---

(22.07.25)

아.. 거의 다 왔는데 안 풀리냐..

import sys
input = sys.stdin.readline
n = int(input())

paper = [list(map(int,input().split())) for _ in range(n)]
typeCount = {-1:0, 0:0, 1:0}

def cut(x, y, n):
  
  if n == 1:
    typeCount[paper[x][y]] += 1
    return 
  type = checkPaper(x, y, n)
  if type != None:
    typeCount[type] += 1
  else:
    for i in range(n):
      for j in range(n):
        print(paper[i][j], end="")
      print("")
    for i in range(n//3):
      for j in range(n//3):
        cut(x+(i*(n//3)), y+(j*(n//3)), n//3)

def checkPaper(x, y, n):
  for i in range(x, x + n):
    for j in range(y, y + n):
      if paper[x][y] != paper[i][j]:
        return None
  return paper[x][y]

cut(0, 0, n)
for value in typeCount.values():
  print(value)

---

역시 안 풀릴 때는 하루 자고 다음 날 풀면 풀린다.

문제를 4-5개 풀면 그 때부터는 머리가 흐려져서 오류가 잘 안 보이더라..

오류 부분은

# cut 의 이 부분
#...
 for i in range(n//3):
      for j in range(n//3):
        cut(x+(i*(n//3)), y+(j*(n//3)), n//3)
#...

도는 값이 매번 3*3이어야 하는데, n//3만큼 돌아서 원하는 범위가 아니게 된 것이다.

배열은 항상 이런게 실수로 잡힌다. 

로직도 로직인데 구현 상의 실수 없게 유의해야겠다.

 

아래가 수정한 코드이다.

import sys
input = sys.stdin.readline
n = int(input())

paper = [list(map(int,input().split())) for _ in range(n)]
typeCount = {-1:0, 0:0, 1:0}

def cut(x, y, n):
  if n == 1:
    typeCount[paper[x][y]] += 1
    return 
  type = checkPaper(x, y, n)
  if type != None:
    typeCount[type] += 1
    return
  else:
    for i in range(3):
      for j in range(3):
        cut(x+(i*(n//3)), y+(j*(n//3)), n//3)

def checkPaper(x, y, n):
  for i in range(x, x + n):
    for j in range(y, y + n):
      if paper[x][y] != paper[i][j]:
        return None
  return paper[x][y]

cut(0, 0, n)
for value in typeCount.values():
  print(value)