ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Python] 백준 16235 나무 재테크
    알고리즘/문제풀이 2021. 8. 20. 22:33
    728x90

    1. 문제 링크

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

     

    16235번: 나무 재테크

    부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터

    www.acmicpc.net


    2. 문제 요약

    4계절에 맞게 구현을 하여 k 년이 지난 후 살아있는 나무 개수를 출력한다.


    3. 아이디어 정리

    1. 나무 나이를 저장할 그래프를 새로 생성한다. - 3차원으로 저장
    2. k 년 동안 4계절을 반복 진행한다.
      1. 봄: 자신의 나이만큼 양분 먹고 나이 + 1 한 칸에 여러 개 나무가 있다면 어린나무부터
      2. 여름: 죽은 나무 = (나이 // 2)로 현재 양분에 넣어준다.
      3. 가을: 나무 번식 - 나이가 5 배수이어야하고, 인접한 8개 칸에 나이가 1 나무 생긴다.
      4. 겨울: 로봇이 양분을 추가한다.
    3. 나무의 수를 세어준다.

    4. 문제 풀이

    4-1. 내 풀이

    """
     return: k년이 지난 후 나무의 개수
    """
    import sys
    
    dx = [1, -1, 0, 0, 1, -1, 1, -1]
    dy = [0, 0, 1, -1, 1, 1, -1, -1]
    
    n, m, k = map(int, sys.stdin.readline().split())  # n*n 땅, m개의 나무, k년
    
    a = list()                                          # 겨울에 추가될 양분
    now_a = [[5] * n for _ in range(n)]                 # 현재 양분은 5로 세팅
    tree = [[[] for _ in range(n)] for _ in range(n)]   # 나무 관련 - 3차원으로 표현(같은 자리에 나무가 여러개 있어서)
    
    # 추가될 양분 관련 입력
    for _ in range(n):
        a.append(list(map(int, sys.stdin.readline().split())))
    
    # 나무 나이 관련 입력
    for _ in range(m):
        x, y, z = map(int, sys.stdin.readline().split())   # (x, y) 나무 위치, 나무 나이
        tree[x - 1][y - 1].append(z)
    
    # k년 동안 4계절 반복하기
    for _ in range(k):
        # 1. 봄: 자신의 나이만큼 양분 먹고 나이 + 1 한칸에 여러개 나무가 있다면 어린나무부터
        for i in range(n):
            for j in range(n):
                if not tree[i][j]:  # 해당 자리에 나무가 없으면 다음 탐색
                    continue
                tree[i][j].sort()   # 어린나무부터 먹기 위함
                # 해당 부분 모두 처음부터 돌면 시간 초과 - 다른 블로그 참고(배열 인덱싱 활용) 
                idx = 0
                while idx < len(tree[i][j]):
                    if tree[i][j][idx] <= now_a[i][j]:
                        now_a[i][j] -= tree[i][j][idx]
                        tree[i][j][idx] += 1
                        idx += 1
                    else:
                        die = tree[i][j][idx:]
                        # 2. 여름: 죽은 나무 = (나이 // 2)
                        for now in die:  
                            now_a[i][j] += (now // 2)
                        tree[i][j] = tree[i][j][:idx]
                        break
        # 3. 가을: 나무 번식 - 나이가 5 배수이어야하고, 인접한 8개 칸에 나이가 1 나무 생김
        for i in range(n):
            for j in range(n):
                for age in tree[i][j]:
                    if age % 5 == 0:  # 5의 배수인 경우, 인접한 8개의 칸에 나이 1 나무 추가
                        for d in range(8):
                            nx = dx[d] + i
                            ny = dy[d] + j
                            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                                continue
                            tree[nx][ny].append(1)
        # 4. 겨울: 로봇이 양분을 추가한다.
        for i in range(n):
            for j in range(n):
                now_a[i][j] += a[i][j]
    
    # 나무의 수 세기
    result = 0
    for i in range(n):
        for j in range(n):
            if tree[i][j]:
                result += len(tree[i][j])
    
    print(result)

     


    5. 결론

    • 구현 문제
    • 나무 나이 저장을 3차원으로 해야한다는 점을 파악해야 한다.
    • 봄~여름 부분 구현이 어려웠던 문제이다. (시간 초과 문제)

    댓글

Designed by Tistory.