DevelopmentAlgorithm

ACMICPC - 스티커(9465)

Algorithm

스티커

어.. 진짜 고민 많이했던 문제였다. 그리디로 하면 분명 안될 것 같고 계속 최선의 방법을 남겨두면서 풀어야 하는게 아닐까 고민했다.

여러 삽질이 있었지만 이번 풀이에 사용한건 한줄씩 자르고 각 상태 3가지를 정의해줬다.

N 열 N 열 N 열
0번째 행 X O X
1번째 행 X X O
상태 0 1 2

그러면 N열에 있는 상태 앞에 올 수 있는 N - 1열의 상태를 정리해볼 수 있다.

N - 1열 N 열
상태 0, 1, 2 0
상태 0, 2 1
상태 0, 1 2

N열에서 선택할 수 있는 최대 점수는 N - 1열의 상태 두 가지중 가장 높은 점수를 택한것을 더해준 값이 될 것이다.
N열 상태 0 : max(N-1열 상태 0, N-1열 상태 1, N-1열 상태 2) + N열에서 자신이 선택한 스티커 점수 (상태 0의 경우는 선택하지 않았으므로 0점)
N열 상태 1 : max(N-1열 상태 0, N-1열 상태 2) + N열에서 자신이 선택한 스티커 점수
N열 상태 2 : max(N-1열 상태 0, N-1열 상태 1) + N열에서 자신이 선택한 스티커 점수

최종적으로는 N 열의 상태 중 가장 점수가 높은값을 출력해주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
cnt = input()

for _ in range(cnt):
    N = input()
    A = []
    for i in range(2):
      tmp = map(int, raw_input().split())
      A.append(tmp)

    # state 0: X X
    # state 1: O X
    # state 2: X O
    D = [[0] * 3 for i in range(N + 1)]
    D[0][1] = A[0][0]
    D[0][2] = A[1][0]

    for i in range(1, N):
        D[i][0] = max(D[i - 1][0], D[i - 1][1], D[i - 1][2])
        D[i][1] = max(D[i - 1][0], D[i - 1][2]) + A[0][i]
        D[i][2] = max(D[i - 1][0], D[i - 1][1]) + A[1][i]
    print max(D[N - 1])

내일도.. 화이팅..!

Share