[백준 1780] 종이의 개수 - python (solved.ac - 실버 2)

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

1780번: 종이의 개수

풀이

문제를 보았을때 알수있는 힌트

N*N의 그래프 형식으로 되어있는 문제 -> 리스트로 그래프를 만들어야한다. x,y형식의 for문 문제를 풀겠네 생각함

반복적으로 자르고, 개수 확인하는 형식이 재귀함수로 풀어야할듯함.

-1,0,1의 수가 n*n의 수이면 결과가 1이라는 것으로 처리했고 아닌경우에는 재귀함수로 3을 나누어 다시 확인하는 형식으로 진행

import sys
input = sys.stdin.readline

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

count = [0,0,0]

def div(size,x,y):
    temp=[0,0,0]
    for i in range(size):
        for j in range(size):
            if list_n[i+x][j+y]==-1:
                temp[0]+=1
            elif list_n[i+x][j+y]==0:
                temp[1]+=1
            else:
                temp[2]+=1
    if max(temp)==size**2:
        count[temp.index(max(temp))]+=1
    elif size==3:
        for i in range(3):
            count[i]+=temp[i]
    else:
        for i in range(0,size,size//3):
            for j in range(0,size,size//3):
                div(size//3,i+x,j+y)
    
div(n,0,0)
for i in range(3):
    print(count[i])

이상없이 문제는 해결되는것같은데 python 에서는 시간초과가 났다. 아마 효율적이지 않은듯하다. 다른 사람들 코드를 보고 이해하며 다시 풀면 통과할수있겠지만.. pypy3에서는 통과하는 것으로 일단 만족하고 다음에 다시 풀게 된다면 최적의 알고리즘을 찾아보겠다.

 

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1780.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리