[실버 III] 2630번. 색종이 만들기

 문제 

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

2630번: 색종이 만들기

 사용 언어 

Python3

 풀이 과정 

재귀는 컴퓨터가 하는건데 내 머리로 짜려니 항상 머리가 아프다...

그래도 어찌저찌 풀어서 채점율 7~80%까지 쭉쭉 오르길래 맞았나!!! 했더니 마지막 순간에 틀렸습니다

어디서 틀린걸까 한참을 보다가 질문하기를 보고 어떤 현자님의 답변에서 힌트를 얻었다.

def cutting(N, papers):
    pieces = []
    global white, blue
    mid = N // 2
	# 각 조각들을 []로 묶어 왼>오 순서대로 pieces에 추가
    pieces.append([papers[i][:mid] for i in range(mid)])
    pieces.append([papers[i][mid:] for i in range(mid)])
    pieces.append([papers[mid+i][:mid] for i in range(mid)])
    pieces.append([papers[mid+i][mid:] for i in range(mid)])

위와 같이 처음 내 코드는 시작하자마자 무조건 잘랐는데, 이러면 처음부터 완성형 색종이(?)인 경우에도 4개로 조각내버린다.

그래서 그 부분만 추가해주니까 바로 맞았습니다!!

새로운 유형 문제를 풀 때마다 시간이 좀 오래걸리는데, 시간을 정하고 양으로 승부하는게 좋을지 그래도 한 문제라도 내 힘으로 풀어보는게 좋을지 딜레마인 상태🤔사실 당연히 내가 풀어서 맞는게 기분 좋지만 그러다보니 하루에 많은 문제를 못 푸는 것 같다...빠른 시일 내에 기준을 정해야 할 듯.

 제출 답안 

from sys import stdin

N = int(stdin.readline())
papers = []
for _ in range(N):
    papers.append(stdin.readline().strip().split())

white = 0
blue = 0

def isCompleted(piece): # 완성형 색종이인가
    pieceSet = set() # set() 자료형 이용
    for i in range(len(piece)):
        pieceSet.update(piece[i]) # 모든 줄 넣어주기
    if len(pieceSet) == 1: # 모두 한 색상이면
        return True
    else: # 섞여있으면
        return False

def cutting(N, papers): # 색종이 자르기
    pieces = []
    global white, blue

    if isCompleted(papers): # 완성형 색종이이면
        if papers[0][0] == '0':
            white += 1
            return
        else:
            blue += 1
            return

    mid = N // 2
    # 각 조각들을 []로 묶어 왼>오 순서대로 pieces에 추가
    pieces.append([papers[i][:mid] for i in range(mid)])
    pieces.append([papers[i][mid:] for i in range(mid)])
    pieces.append([papers[mid+i][:mid] for i in range(mid)])
    pieces.append([papers[mid+i][mid:] for i in range(mid)])
    
    for j in range(4): # 항상 네 조각으로 나뉨
        # print(f'pieces[{j}]: {pieces[j]}')
        cutting(mid, pieces[j])

cutting(N, papers)
print(white)
print(blue)

 다른 사람 답안 & 느낀점 

따로 새롭게 공부한 내용은 없고 제출 현황에서 시간이 76ms인 python3 코드를 읽어보았는데 내 코드의 찜찜한 중복 현상의 원인을 파악하고 더 깔끔하게 고칠 수 있었다.

(색종이 count 후에 return을 사용하면 나눈 직후에 isCompleted 함수를 또 호출할 필요가 없음)

그런데 소요 시간은 계속 똑같은 걸 보면 내가 원하는 형식대로 만들기 위해 list comprehension을 사용한 부분, set()을 여러번 만드는 부분에서 시간이 좀 걸리는 것 같다.

 

어쨌든 처음 내가 생각한 방식도 다음의 check 함수와 같이 길이가 1이면 끝, 비교하다가 다른 게 나오면 False 반환하기였는데 나는 무조건 진짜 자른다(자른 후의 리스트를 새로 만들어줘야 함)라고 생각해서 더 복잡했던 것 같다.

다음과 같이 좌표로 접근해서 풀면 더 간단하고 시간도 빠른 것 같다. 참고참고!!😎

import sys
input = sys.stdin.readline

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

def check(n, x,y):
  if n == 1:
    return True
  temp = paper[x][y]

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

  return True
def cut(n, x, y):
  if check(n,x,y):
    result[paper[x][y]] += 1
    return
  
  cut(n//2, x, y)
  cut(n//2, x, y+n//2)
  cut(n//2, x+n//2, y)
  cut(n//2, x+n//2, y+n//2)

cut(n,0,0)
print(result[0])
print(result[1])

출처: 백준 2630번 dnjsdud2257님의 소스코드

 

그리고 최근 set() 자료형을 여러번 사용하며 느낀점은 교집합, 합집합, 차집합이나 len을 사용해서 개수를 쓰긴 쉽지만 set() 안의 원소에 접근하려면 결국 list()나 tuple()을 사용해야 한다는 불편함을 느꼈다. 심지어 원소가 하나 이상이면 정렬 등이 필요한... 그래서 그 때 그 때 진짜 set()이 최선인지 생각해보는게 중요할 듯!