• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 9465번 : 스티커 with python3

06 Sep 2018

Reading time ~1 minute

문제 : https://www.acmicpc.net/problem/9465

주 발상

  • greedy로 푸는 것이다.
  • ans[j][i]는 i의 길이의 스티커에서 j번째 상황에서 낼 수 있는 가장 큰 값을 저장해 놓는다.

def solved(d, n):
    ans = [[0]*(n+1) for _ in range(3)]
    for i in range(1, n+1):
        ans[0][i] = max(ans[0][i-1], ans[1][i-1], ans[2][i-1])
        ans[1][i] = max(ans[0][i-1], ans[2][i-1]) + d[0][i-1]
        # 아래쪽을 뜯었으니(xo) ans[0][i-1], ans[2][i-1]
        # 즉 xx or ox중 하나의 경우의 수를 선택 해야한다.
        # 그래서 그 중 큰거 더하고 !

        # d[0][i-1]은 아래를 뜯었으니 그 스티커의 값을 넣는 것이다.
        ans[2][i] = max(ans[0][i-1], ans[1][i-1]) + d[1][i-1]

    print(max(ans[0][n], ans[1][n], ans[2][n]))

for i in range(int(input()), 0, -1):
    solved([list(map(int, input().split())) for i in range(2)], int(input()))

ans는 i번째 줄의 스티커를 뜯을 때, 각각의 경우에 따른 최대값을 나타낸다.

ans[0][i]는 스티커가
x
x
하나두 안뜯긴 것

ans[1][i]는 스티커가
o
x
위만 뜯긴 것

ans[i][1]는 스티커가
x
o
아래만 뜯긴 것



algorithm백준 Share Tweet +1