[코테준비] 7. 백준- 나무 재테크(16235) python "삼성 SW 역량 테스트 기출 문제"

나무 재테크

• 링크:https://www.acmicpc.net/problem/16235
• 난이도:골드 3
• 분류: 구현
• 직접 푼 여부: O 그런데 시간초과나서 다른 글 참고함

풀이 노트

아래노트 필기처럼 생각하고 풀다가, 시간 초과가 났다. 시간초과난 코드는 아래와 같다. 시간복잡도가 복잡도가 k*n*n*m*8*(1000log1000)인데, 그러면 10*(3+1+1+2+3) = 10*10 가 되었기 때문에.. 당연히 시간초과가 난 것..!

 

그래서 그 밑에는 시간초과가 나지 않는 코드를 작성했다!

deque가 appendleft가 있는지 몰랐는데, 있고 이것의 시간복잡도는 무려 O(1)!! 만세다

그리고 heapq를 사용했던 것은 "어린"나무부터 양분을 먹는다는 조건 때문이였는데 이는 사실 별로 sorting이 필요한 일이 아니였다. 왜냐면, 처음 심어지는 나무는 다 다른 곳에 심어지고, 새로 심어지는 나무는 모두 1이기때문에 + 원래 있던 나무보다 어리기 때문에, 그냥 deque에 left에 append하고 left pop을 하며 꺼내주면 되는것이다! 그럼 왼쪽부터 오른쪽까지 점점 나이가 상승하는 나무 list완성!

초반에 문제를 보며 생각한 과정을 정리한 노트이다

 

 

코드 (시간초과난 코드)

# 16235번 - heapq는version ( list&sort 다른풀이에서)
# 시간초과
import sys
import heapq
sys.stdin = open("./input.txt")
input = sys.stdin.readline

# input & 준비 -------
n, m, k = map(int, input().split())
# n: 땅크기, m: 나무 개수, k: 몇년 후
a = [list(map(int, input().split())) for _ in range(n)]
# a: 양분 채워지는 양분의 양
foodmap =[[5]*n for _ in range(n)]

tree = [[[] * n for _ in range(n)] for _ in range(n)]
# 각 위치에있는 tree 넣기
for _ in range(m):
    i, j, age = map(int, input().split())
    # tree[i-1][j-1].append(age)
    heapq.heappush(tree[i - 1][j - 1], age)
# 좌 대 상 대 우 대 하 대 (시계 방향회전 !!)
dr =[0,-1,-1,-1, 0,1,1,1]
dc =[-1,-1,0,1,1,1,0,-1]
# 일년 나기 *k -------
for year in range(k):
    # 봄 & 여름  ------
    for i in range(n):
        for j in range(n):
            food = foodmap[i][j]
            now = tree[i][j]
            tree[i][j] =[]
            diefood = 0
            for ii in  range(len(now)): # 한개라도 있으면,
                tr = heapq.heappop(now)
                if food -tr <0:
                    # 양분 부족하면, 양분으로 만듦
                    diefood+=tr//2
                else:
                    # 양분 있으면, 먹고 나이 +1
                    food-=tr
                    heapq.heappush(tree[i][j], tr+1) # tree update
            foodmap[i][j] = food + diefood # food update (남은 양분 + 죽어서 생긴 양분)

    # 가을 &  겨울  ------
    for i in range(n):
        for j in range(n):
            #가을
            for ftr in tree[i][j]:
                if ftr%5 ==0: # 어차피 tree가 있다면, 나이는 1이상
                    #5의 배수라면,
                    for dir in range(8):
                        newr = i+ dr[dir]
                        newc = j+dc[dir]
                        if (0<=newr<n) and (0<=newc<n):
                            # 범위 안에 들어올 때만 나무 심어짐
                            heapq.heappush(tree[newr][newc],1)
            #겨울
            foodmap[i][j]+= a[i][j]



# 살아있는 나무개수 count -------
ans = 0
for i in range(n):
    for j in range(n):
        ans += len(tree[i][j])
print(ans)

 

시간초과나지 않는 코드💻

그런데 이 코드도 python3으로 돌리면 시간 초과가 뜬다..!

# 16235번 - deque버전
import sys
from collections import deque
sys.stdin = open("./input.txt")
input = sys.stdin.readline

# input & 준비 -------
n, m, k = map(int, input().split())
# n: 땅크기, m: 나무 개수, k: 몇년 후
a = [list(map(int, input().split())) for _ in range(n)]
# a: 양분 채워지는 양분의 양
foodmap =[[5]*n for _ in range(n)]

tree = [[deque() for _ in range(n)] for _ in range(n)]
# 각 위치에있는 tree 넣기
for _ in range(m):
    i, j, age = map(int, input().split())
    # tree[i-1][j-1].append(age)
    tree[i - 1][j - 1].append(age) #어차피 하나니까 그냥 age append~
# 좌 대 상 대 우 대 하 대 (시계 방향회전 !!)
dr =[0,-1,-1,-1, 0,1,1,1]
dc =[-1,-1,0,1,1,1,0,-1]
# 일년 나기 *k -------
for year in range(k):
    # 봄 & 여름  ------
    for i in range(n):
        for j in range(n):
            food = foodmap[i][j]
            for ii in range(len(tree[i][j])):
                if foodmap[i][j]>=tree[i][j][ii]:
                    #양분있으면, (앞에서 부터 체크하니까 작은 것 부터 보는 것!)
                    foodmap[i][j]-=tree[i][j][ii] # 양분 없어짐
                    tree[i][j][ii] +=1 #나이 +=1
                else:
                    # 모자라면, 한번에 다 처리
                    for _ in range(ii,len(tree[i][j])):
                        foodmap[i][j] += tree[i][j].pop()//2 #뒤에서 부터 pop
                    break
    # 가을 &  겨울  ------
    for i in range(n):
        for j in range(n):
            #가을
            for ftr in tree[i][j]: #앞에서부터 나옴(순서는 상관 없음)
                if ftr%5 ==0: # 어차피 tree가 있다면, 나이는 1이상
                    #5의 배수라면,
                    for dir in range(8):
                        newr = i+ dr[dir]
                        newc = j+dc[dir]
                        if (0<=newr<n) and (0<=newc<n):
                            # 범위 안에 들어올 때만 나무 심어짐
                            tree[newr][newc].appendleft(1)
            #겨울
            foodmap[i][j]+= a[i][j]



# 살아있는 나무개수 count -------
ans = 0
for i in range(n):
    for j in range(n):
        ans += len(tree[i][j])
print(ans)