[CLASS 3]백준 1780번, 1931번

1780번 : 종이의 개수

 

저번에 본 [CLASS 3]백준 2630번 - 색종이 만들기 와 상당히 유사한 문제이다. 재귀를 통해 색종이를 계속 9등분하면서 해당 색종이 안에 같은 수만 있는지 확인해주면 된다. 저번엔 푸는데 힘들었지만 이번엔 쉽게 풀었다!

 

내 코드(느림):

from sys import stdin
input = stdin.readline

n = int(input())
mat = [list(map(int,input().split())) for _ in range(n)]
# 카운터 리스트. 각각 -1, 0, 1 인 종이의 개수와 대응
counts = [0,0,0]

dX = [0,1,2]
dY = [0,1,2]

def find(startX,startY,n):
    num = mat[startY][startX]

    for y in range(startY,startY+n):
        for x in range(startX,startX+n):
            if mat[y][x] != num:
                d = n // 3
                for dy in dY:
                    for dx in dX:
                        find(startX+dx*d,startY+dy*d,d)
                return

    counts[num+1] += 1

find(0,0,n)
print(counts[0],counts[1],counts[2],sep='\n')

 

이렇게 작성하여 제출했는데 무려 5392ms나 걸렸다. 다른 분들의 코드를 확인해봤는데 2000ms정도가 평균인 것 같아서 왜 그런지 생각해봤는데, 이유는 n 이 1 일때도 쓸데없이 반복문에 진입해서 필요없는 연산을 하였기 때문이었다. 그래서 다음과 같이 수정했다.

 

내 코드:

from sys import stdin
input = stdin.readline

n = int(input())
mat = [list(map(int,input().split())) for _ in range(n)]
# 카운터 리스트. 각각 -1, 0, 1 인 종이의 개수와 대응
counts = [0,0,0]

dX = [0,1,2]
dY = [0,1,2]

def find(startX,startY,n):
    num = mat[startY][startX]
    # n이 1일 경우 바로 return
    if n == 1:
        counts[num+1] += 1
        return

    for y in range(startY,startY+n):
        for x in range(startX,startX+n):
            if mat[y][x] != num:
                d = n // 3
                for dy in dY:
                    for dx in dX:
                        find(startX+dx*d,startY+dy*d,d)
                return

    counts[num+1] += 1

find(0,0,n)
print(counts[0],counts[1],counts[2],sep='\n')

 

그래서 이렇게 변경하였다. n이 1일경우 반복문에 진입하지 않고, 바로 count에 1을 더한 후 리턴하였다. 이렇게 수정하니 시간이 3164ms로 줄었다.

 

1931번 : 회의실 배정

 

그리디로 풀 수 있는 문제이다. 근데 이 문제는 함정이 있다. 회의 시작시간과 끝나는 시간이 같을 수도 있다는 것이다. 이게 회의가 맞는지조차 불분명하지만.. 이것때문에 자신있게 제출한 답안이 왜 틀렸는지 한참 고민했다..

 

내 코드:

from sys import stdin
input = stdin.readline

meetings = []
for _ in range(int(input())):
    meeting = tuple(map(int,input().split()))
    meetings.append(meeting)
    
# 끝나는 시간(같다면 시작하는 시간)을 기준으로 정렬
meetings.sort(key=lambda meeting: meeting[0])
meetings.sort(key=lambda meeting: meeting[1])

count, lastEnd = 0, 0
for meeting in meetings:
    if meeting[0] >= lastEnd:
        count += 1
        lastEnd = meeting[1]

print(count)

 

처음에는 끝나는 시간만 고려해서 정렬했는데, 사실 회의 진행 시간이 0인 비정상적인 회의만 없다면 그렇게 해도 맞지만, 이 문제는 그렇지 않기 때문에 끝나는 시간이 같다면 시작하는 시간순으로 정렬되어 있어야 한다.