본문 바로가기
알고리즘 공부/Python

백준 16235 나무 재테크 (Python)

by 킴워니 2020. 5. 4.
나무 재테크는 결단코 좋은 재테크는 아닌 것 같다.
그래도 오랜만에 원샷원킬해서 기분이 좋다.

 

문제는 여기!

 

16235번: 나무 재테크

부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든

www.acmicpc.net

 

말만 잘 들으면 된다는 시뮬레이션 문제입니다.

시간 초과가 나온다면 어쩔 수 없겠지만, 만약 틀린 답이라면 내가 어디선가 말을 덜 들었다는 것!

 

아이디어

1. 봄과 여름에서 같은 데이터를 써야한다(죽은 나무) 그렇기 때문에 둘을 하나의 함수로 묶었다. 

2. 나머지는 적절한 내장 메서드(sort라든가..sort라든가..)를 써주며 말을 잘 들으면 된다!

 

 

 

구현 코드

더보기
def spring_summer(): #봄, 여름 함수
    global soils
    global trees
    dead_trees = [[[] for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            trees[i][j].sort()
            for idx in range(len((trees[i][j]))):
                if soils[i][j]>= trees[i][j][idx]:
                    soils[i][j] -= trees[i][j][idx]
                    trees[i][j][idx] += 1
                else:
                    dead_trees[i][j].append(idx)
            for idx in range(len(dead_trees[i][j])-1,-1,-1): #죽은 나무가 있을 경우 해당 칸 안만 바뀌기 때문에 칸별로 봄여름을 한번에 진행했다. 
                temp = trees[i][j][dead_trees[i][j][idx]]
                del trees[i][j][dead_trees[i][j][idx]]
                soils[i][j] += temp//2
    return


delta = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,-1),(-1,1)]


def autumn(): #가을 함수
    new_trees = [[[] for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for tree in trees[i][j]:
                if tree%5 == 0:
                    for dl in delta:
                        newi = i + dl[0]
                        newj = j + dl[1]
                        if -1<newi<N and -1<newj<N:
                            new_trees[newi][newj].append(1)
    for i in range(N):
        for j in range(N):
            trees[i][j].extend(new_trees[i][j])
    return


def winter(): #겨울함수
    for i in range(N):
        for j in range(N):
            soils[i][j] +=fertilizer[i][j]
    return


N, M, K = map(int, input().split())
fertilizer = [list(map(int, input().split())) for _ in range(N)]
soils = [[5 for _ in range(N)] for _ in range(N)]
trees = [[[] for _ in range(N)] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    trees[x-1][y-1].append(z)
for _ in range(K):
    spring_summer()
    autumn()
    winter()
ans = 0
for i in range(N):
    for j in range(N):
        ans += len(trees[i][j])

print(ans)

1초 넘게 나오는 걸 봐서 좋은 코드는 아니다. 특히 sort 메서드를 쓰지 않는 순간 바로 시간초과 날 것 같긴하다. (그러나 그런 메서드 쓰라고 파이썬이 존재하는 것..아닐가여..)

댓글