1. 개요
2행 n열로 배치된 스티커가 존재하고, 각 스티커에는 점수가 있음. 그리고 각 스티커를 뗄 때 인접 스티커는 사용 불가.
이런 경우에 스티커들 중에서 서로 인접하지 않은 것들을 뽑아서 최대값을 구하려면 어떻게 해야하는가?
그리고 그렇게 할 때 최대값은?
2. 접근 방법
문제의 핵심은 동적 계획법 (DP)을 활용하는 것
각 열마다 세 가지 경우 고려할 것.
- dp[i][0]: i번째 열에서 아무 스티커도 선택하지 않은 경우
- dp[i][1]: i번째 열에서 상단 스티커 선택한 경우
- dp[i][2]: i번째 열에서 하단 스티커 선택한 경우
이때, 점화식을 짜면서 중요한 것은 현재의 선택에 대한 현재까지의 스티커 숫자 합의 계산은 이전 선택의 영향을 받는 다는 것.
위 사실을 인지한 채로 이하 점화식을 이해해야 함.
3. 점화식 및 초기화
3.1 초기값
첫 열에 대해
- dp[0][0] = 0
- dp[0][1] = top[0]
- dp[0][2] = bottom[0]
초기값을 설정해주는 이유는 , 이후에 이어지는 점화식에서
i라는 현재 열에 대한 정보가i-1이라는 정보를 기반으로 생성되는데0으로 시작하는 경우-1번째 열에 대한 정보는 고려할 수 없기에0번째 열에 대한 합산 값은 초기화 해줌.
3.2 점화식
열 i (i ≥ 1)에서
-
아무것도 선택하지 않는 경우:
dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
→ 이전 열의 모든 경우 중 최댓값 그대로 가져옴. -
상단 선택하는 경우:
dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + top[i]
→ 상단 선택 시, 이전 열에서 상단은 선택하면 인접됨.
따라서 이전 열에서는 아무것도 선택하지 않았거나 하단을 선택한 경우만 가능함. -
하단 선택하는 경우:
dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + bottom[i]
→ 하단 선택 시, 이전 열에서는 하단을 선택하면 안되므로, 아무것도 선택하지 않았거나 상단을 선택한 경우 고려함.
최종 정답은 dp[n-1]의 세 값 중 최댓값임.
4. 전체 코드
아래는 문제 풀이 전체 코드임.
import sys
def main():
N = int(sys.stdin.readline().rstrip())
for _ in range(N):
n = int(sys.stdin.readline().rstrip())
# dp[i][0]: 무선택, dp[i][1]: 상단 선택, dp[i][2]: 하단 선택
dp = [[0, 0, 0] for _ in range(n)]
top = list(map(int, sys.stdin.readline().rstrip().split()))
bottom = list(map(int, sys.stdin.readline().rstrip().split()))
# 초기화: 첫 열 처리
dp[0][0] = 0
dp[0][1] = top[0]
dp[0][2] = bottom[0]
# 1열부터 시작 (이전 열과의 관계 고려)
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + top[i]
dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + bottom[i]
# 최종 정답 출력: 마지막 열의 세 경우 중 최대값
print(max(dp[n-1][0], dp[n-1][1], dp[n-1][2]))
if __name__ == "__main__":
main()5. 결론
- 문제는 인접 제약 조건 때문에 각 열마다 3가지 상태를 고려해야 함.
- DP 상태 정의에 신경쓰고 제약조건을 고려하여 세분화해 저장할 것.
