백준 28325 (호숫가의 개미굴)

백준 28325 (호숫가의 개미굴)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/28325

문제 접근

그래프 형태의 개미굴이 있습니다. 각 개미굴에는 쪽방이 달려 있을 수도 있고, 없을 수도 있습니다. 개미굴이나 쪽방에 개미를 한 마리씩 넣을 수 있습니다. 개미굴과 쪽방, 개미굴과 개미굴을 연결하는 간선의 끝에는 통행에 방해가 되므로 최대 한 마리의 개미만 넣을 수 있습니다. 즉, 그래프의 간선(edge)에 달린 점(vertex)은 최대 하나만 선택할 수 있습니다. 이 때, 개미굴에 살고 있는 최대 개미의 수를 구하는 것이 문제입니다. 즉, 총 선택한 점의 수를 최대화하는 것이 문제가 됩니다.

각 개미굴은 인접한 개미굴에 영향을 받습니다. i번째 개미굴을 예시로 설명해보겠습니다. i번째 개미굴은 i-1번째 개미굴의 선택 유무에 따라 영향을 받습니다. 만약 i-1번째 개미굴을 선택한다면, i번째 개미굴은 자연스럽게 개미굴은 선택할 수 없습니다. 즉 i번째 개미굴에 연결되어 있는 쪽방을 모두 선택해야 합니다. i-1번째 개미굴을 선택하지 않는다면 두 가지로 분기가 됩니다. i번째 개미굴을 선택하는 경우와, 선택하지 않는 경우로 나뉠 수 있습니다. 하지만 현재 시점(i)에서 직전의 개미굴 상태(i-1)가 중요하지, 딱히 그보다 훨씬 예전의 개미굴 상태는 중요하지 않습니다. 그렇다면 직전의 상태만 잘 저장해둔다면(memoization), 최악의 경우 2^250000의 시간이 걸리지 않고, O(n)의 시간으로 충분히 문제를 해결할 수 있다는 의미입니다.

다이나믹 프로그래밍으로 문제를 해결할 수 있을 듯 합니다. 점화식을 세워볼 수 있습니다. dp[room][0]은 room번째의 개미굴을 선택했을 때, 최대 값을 저장하고, dp[room][1]은 room번째의 개미굴을 선택하지 않았을 때 최대 값을 저장하는 2차원 배열 dp를 선언했습니다.

dp[room][0]은 dp[room-1][1]인 값에 +1을 한 값이 될 것입니다. 왜냐하면 개미굴을 선택하는 경우는 단 하나의 점만 추가가 되기 때문입니다. dp[room][1]은 dp[room-1][0]과 dp[room-1][1]의 값에 영향을 받습니다. 왜냐하면 현재 선택이 자유로운 상태기 때문입니다. 즉 바로 직전의 개미굴을 선택한 경우와, 직전의 개미굴을 선택하지 않은 경우의 값을 비교해서 나온 큰 값에, 현재 개미굴의 쪽방의 수를 더해준 값이 될 수 있습니다.

구현 시, 첫 방을 선택하지 않은 경우와, 선택한 경우 두 가지로 나누어서 구현을 했습니다. 두 경우에 대해 값을 구한 후, 둘 중 최댓값을 출력하도록 구현하였습니다.

소스 코드

import sys 

def solution(a,b) :
    global n,C,dp
    dp[1][0]=a
    dp[1][1]=b
    
    for room in range(2,n+1) :
        dp[room][0]=dp[room-1][1]+1
        dp[room][1]=max(dp[room-1][0],dp[room-1][1]) + C[room]
    
    if a==0 : #첫 방 선택하지 않음
        return max(dp[n][0],dp[n][1])
    else : #첫 방 선택한 경우
        return dp[n][1]

n=int(input())
C=[0]+list(map(int,sys.stdin.readline().split())) #idx가 방의 번호를 나타냄
dp=[[0,0] for _ in range(n+1)]
print(max(solution(0,C[1]), solution(1,0)))

마무리하며

누가 볼 지는 모르겠지만, 질문 사항이 있으면 댓글로 남겨주시길 바랍니다. 요즘 디지털 디톡스를 열심히 하는 중입니다.. 원래 손코딩을 더 좋아하긴 했는데 손코딩을 하면서 살고 있답니다.. 카페에서 음침하게 라디오헤드 앨범 들으면서 코딩해야겠습니다 …