백준 16235 : 나무 재테크(파이썬)

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

16235번: 나무 재테크

 이해하는 것은 어렵지 않았지만, 구현이 상당히 까다로웠던 문제.

패키지들을 지양하고 문제를 풀려고 하니 더욱 맞추기 어려웠다. 결국 제한시간안에 문제를 풀지 못했다.

정답 처리 받는데 까지 걸린 시간... 6시간..

그럼에도 잘한점을 찾자면, 어쨌든 해결했고 나름의 노하우(?) 하나 더 쌓았다는 것?

이번에 문제 풀면서 정말 많은 점을 알게 되었다.

 

 1. 리스트 메모리 주소 할당

 문제 풀던 습관대로 나무가 있을 NxN 리스트 안에 각각의 요소들이 또 리스트로 존재하는 형태로 구성하기 위해 습관처럼 다음과 같이 작성했다. 해당 리스트 이름을 tree_b라고 지었다.

tree_b = [[[]] * n for _ in range(n)]

 이렇게 하면 아예 정답조차 접근을 못한다. 메모리 할당 주소를 찾아보면 각 행의 요소 리스트들은 전부 동일한 주소값을 갖게 된다. 전공이 컴공이 아니라 왜 그런지는 아직 이유를 잘 모르겠으나, 사용자의 편의성이 강조된 만큼 메모리도 동일하게 할당해주도록 작동하는 것 같았다. 따라서 각각의 요소들도 직접 지정해주어야 한다. 

tree_b = [[[] for _ in range(n)] for _ in range(n)]

 

 2. 함수와 반복문의 최소화

 함수로 보기 편하게 만들어 사용하게되면 논리는 수월하게 짜이나 함수간 참조하면서 이동하는 시간이 추가되어 적정시간 안에 못 풀게 될 수 있다는 것을 확인했다. 테스트 케이스 1000년으로 돌렸을 때 알게 되었다. 그래서 프로그램 구성을 나무가 번식하는 함수(Birth) , 사계절 한 바퀴 도는 함수(season), 해답 찾는 영역(solve)으로 나누어서 풀었다가, 함수 자체를 지워버렸다.

 그리고 반복문을 최소화 하였다. 문제를 풀 때 봄과 여름, 가을과 겨울은 묶어서 반복문을 구성해도 계산상에는 문제가 없다는 것을 확인했다. 그래서 사계절 루틴은 다음과 같이 단순화가 가능할 수 있었다.

# Spring & Summer
for i in range(n) :
    for j in range(n) :
        new_f = 0
        temp = []
        tree_b[i][j].sort()
        for age in tree_b[i][j] :
            if board[i][j] - age >= 0 :
                board[i][j] -= age
                temp.append(age + 1)
            else :
                new_f += age // 2
        tree_b[i][j] = temp
        board[i][j] += new_f
# Autumn & Winter
new_b = []
for i in range(n):
    for j in range(n):
        board[i][j] += food[i][j]
        for age in tree_b[i][j] :
            if age % 5 == 0 : # 번식, 위치는 인접한 칸
                for r, c in d :
                    nx = i + r
                    ny = j + c
                    if 0 <= nx < n and 0 <= ny < n :
                        new_b.append([nx, ny])
if new_b :
    # print(new_b)
    for x, y in new_b :
        tree_b[x][y].append(1)

 

 3. 전체코드

 메모리 224012 KB / 시간 1292 ms

좋은 공부가 되었다.

n, m, k = map(int, input().split())
food = [list(map(int, input().split())) for _ in range(n)]
# food log
board = [[5] * n for _ in range(n)]
tree_b = [[[] for _ in range(n)] for _ in range(n)]
for i in range(m):
    r, c, a = map(int, input().split())
    tree_b[r - 1][c - 1] = [a]

d = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
for _ in range(k) :
    # Spring & Summer
    for i in range(n) :
        for j in range(n) :
            new_f = 0
            temp = []
            tree_b[i][j].sort()
            for age in tree_b[i][j] :
                if board[i][j] - age >= 0 :
                    board[i][j] -= age
                    temp.append(age + 1)
                else :
                    new_f += age // 2
            tree_b[i][j] = temp
            board[i][j] += new_f
    # Autumn & Winter
    new_b = []
    for i in range(n):
        for j in range(n):
            board[i][j] += food[i][j]
            for age in tree_b[i][j] :
                if age % 5 == 0 : # 번식, 위치는 인접한 칸
                    for r, c in d :
                        nx = i + r
                        ny = j + c
                        if 0 <= nx < n and 0 <= ny < n :
                            new_b.append([nx, ny])
    if new_b :
        # print(new_b)
        for x, y in new_b :
            tree_b[x][y].append(1)

cnt = 0
for i in range(n) :
    for j in range(n) :
        cnt += len(tree_b[i][j])
print(cnt)