소프티어 나무 수확 Python 풀이

문제를 너무 오래 붙잡고 있어서 열받았다. 연습문제 톡에 그냥 정답코드 올려버리려다가 참는다...

그래도 다른 사람을 배려해서 힌트를 3 단계로 나눠서 주겠다.

 

1번 힌트

DP를 사용한다.

2번 힌트

그래 DP인건 이미 알았겠지. 하하..

DP가 3차원 배열이다.

3번 힌트

3차원인 것도 알았는데 위치말고 뭘 넣어야할지 몰랐을 수도 있겠지. 하하..

DP[r][c][스프링쿨러 설치 여부]

 

 

 

 

 

 

 

 

 

 

 

 

코드도 첨부한다.

N = int(input())
tree = [[0] * (N+1) for _ in range(N+1)]

for i in range(1, N+1):
    tree[i][1:] = list(map(int, input().split()))


did = [[0] * (N+1) for _ in range(N+1)]
yet = [[0] * (N+1) for _ in range(N+1)]

did[1][1] = tree[0][0] * 2
yet[1][1] = tree[0][0]


def solution():
    for r in range(1, N+1):
        for c in range(1, N+1):
            yet[r][c] = max(yet[r-1][c], yet[r][c-1]) + tree[r][c]
            did[r][c] = max(max(did[r-1][c], did[r][c-1]) + tree[r][c], max(yet[r-1][c], yet[r][c-1]) + tree[r][c]*2)

    print(did[N][N])

solution()

 

너무 짧아서 어이없다.

참고로 나는 2차원 배열 2개로 나눴다.

- did : 스프링 쿨러를 설치한 경우 최대 값

- yet : 스프링 쿨러를 설치하지 않은 경우 최대 값

 

왼쪽과 위쪽 값을 사용해야 하므로 그냥 배열을 N+1 크기로 만들었다.

1. r, c 2중  for문 탐색

2. yet[r][c] => yet은 쭉~~~ 스프링 쿨러가 설치되지 않은 상태에서 최대값이어야 한다. 그러므로 위쪽, 왼쪽에 아직 스프링 쿨러를 설치하지 않은 수도의 경로 중 더 큰 값을 선택하고, 현재 위치에 수도를 연결한다.

3. did[r][c] => 여기가 좀 복잡하다. 무려 4개의 값을 비교해야한다. 스프링 쿨러를 설치한 경우다. 그러나 앞에서 스프링 쿨러를 이미 설치했을 수도 있고, 지금에서야 스프링 쿨러를 설치할 수도 있다. 두 경우 다 반영해야한다. 어떻게?

  - 앞에 이미 스프링 쿨러를 설치해놨다면, 그 값과 지금 위치에 수도를 연결해서 값을 얻을 수 있다. 왼쪽, 위쪽 중 더 큰 값을 사용하고, 현재 위치의 씨앗 수확량을 더한다.

  - 앞서 스프링 쿨러를 설치하지 않았을 경우, 지금 위치에 스프링쿨러를 설치해볼 수 있다. 마찬가지로 왼쪽, 위쪽 중 더 큰 값을 사용하고, 현재 위치의 씨앗 수확량의 2배 한 값을 더한다.

마지막으로 무조건 스프링쿨러 1개는 설치한 상태여야 하므로, 스프링 쿨러를 설치한 값 중 (N, N)의 값을 출력한다.

 

끝